如果数组长度为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;
}
