旅游网站如何做推广,好享管家安卓下载,做电路方案设计的网站,个体可以做几个网站二分搜索 1. 有序数组中确定 num 存在还是不存在2. 有序数组找大于等于 num 的最左位置3. 有序数组找小于等于 num 的最右位置4. 二分搜索不一定发生在有序数组上 如果数组长度为n#xff0c;二分搜索搜索次数是log2n次#xff0c;时间复杂度O(log n) 1. 有序数组中确定 num … 二分搜索 1. 有序数组中确定 num 存在还是不存在2. 有序数组找大于等于 num 的最左位置3. 有序数组找小于等于 num 的最右位置4. 二分搜索不一定发生在有序数组上 如果数组长度为n二分搜索搜索次数是log2n次时间复杂度O(log n) 1. 有序数组中确定 num 存在还是不存在
public static boolean exist(int[] arr, int num) {if (arr null) {return false;}int l 0, r arr.length - 1, m 0;while (l r) {// 中点位置m l ((r - l) 1); // l加一半距离等价于相加除二数组很长时可防止溢出if (arr[m] num) {return true;} else if (arr[m] num) {r m - 1;} else {l m 1;}}return false;}2. 有序数组找大于等于 num 的最左位置
public static int findLeft(int[] arr, int num) {if (arr null) {return -1;}int l 0, r arr.length - 1, m 0;int ans -1;while (l r) {m l ((r - l) 1);if (arr[m] num) {ans m; // // 这个范围内 临时满足条件的位置 需要继续二分r m - 1;} else if (arr[m] num) {l m 1;}}return ans;}3. 有序数组找小于等于 num 的最右位置
public static int findRight(int[] arr, int num) {if (arr null) {return -1;}int l 0, r arr.length - 1, m 0;int ans -1;while (l r) {// 中点位置m l ((r - l) 2);if (num arr[m]) {r m - 1;} else if (num arr[m]) {ans m; // 这个范围内 临时满足条件的位置 需要继续二分l m 1;}}return ans;}4. 二分搜索不一定发生在有序数组上
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums找到峰值元素并返回其索引。数组可能包含多个峰值在这种情况下返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] nums[n] -∞ 。你必须实现时间复杂度为 O(log n) 的算法来解决此问题。力扣 162.寻找峰值
public int findPeakElement(int[] arr) {int n arr.length;// 如果开头或者结尾满足条件直接返回if (arr.length 1) {return 0;}if (arr[0] arr[1]) {return 0;}if (arr[n - 1] arr[n - 2]) {return n - 1;}// 二分搜索int l 1, r n - 2, m 0, ans -1;while (l r) {// 中点位置m l ((r - l) 2);// 起点位置(l)和中点m之间必有峰值, r左移继续二分if (arr[m - 1] arr[m]) {r m - 1;// 中点m和终点位置(r)之间必有峰值, l右移继续二分} else if (arr[m] arr[m 1]) {l m 1;// 此时为峰值,返回索引位置} else {ans m;break;}}return ans;}
