二分查找总结
一般在下面这些题目中可以直接使用二分查找法，最方便并且时间复杂度也非常低
- 在一个有序数组中，找到某个数是否存在
- 在一个有序数组中，找到>=某个数最左侧的位置
- 在一个有序数组中，找到<=某个数最右侧的位置
- 局部最小值问题
题目：
给定一个有序数组arr和一个指定的数num，判断num是否存在于arr中
例如：arr=[1,3,5,6,10,100]，num=10，返回true
? arr=[1,3,5,6,10,100]，num=4，返回false
解析
找到关键字：有序数组 、判断是否存在
一般对于有序数组中对某个数做操作的问题，都可以使用二分查找法解决
- 代码
public static boolean isExist(int[] arr, int num) {
if(arr == null || arr.length == 0) {
return false;
}
int L = 0;
int R = arr.length - 1;
// 这里是<，那么当L==R的时候会退出循环，最终判断该数是符合条件即可
while (L < R) {
int mid = L + ((R - L) >> 1);
if(arr[mid] > num) {
R = mid - 1;
} else if(arr[mid] < num) {
L = mid + 1;
} else {
return true;
}
}
return arr[L] == num;
}
