二分法
1.二分法查找
时间复杂度（log2N）
public static int binarySearch(int[] arr,int L,int R,int key){
if (L >R)
return -1;
int mid = L + ((R - L) >> 1);
int index;
if (arr[mid] == key) {
return mid;
}else if (arr[mid] < key)
index = binarySearch(arr, mid+1, R, key);
else {
index = binarySearch(arr, L, mid-1, key);
}
return index;
}
2.有序数组中，二分法找>=某个数最左侧位置或<=某个数最右侧
方法：二分到左侧没有数，不同于常规二分法找到就返回，一定分到不能分为止。
public static int left(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while(left <= right) {
int mid = (left + right) / 2;
if (arr[mid] >= target) {
right = mid - 1;
}else if(arr[mid] < target){
left = mid + 1;
}
}
return left;
}
public static int right(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while(left <= right) {
int mid = (left + right) / 2;
if (arr[mid] <= target) {
left = mid + 1;
}else if(arr[mid] > target){
right = mid - 1;
}
}
return right;
}
3.局部最小值
一个arr无序，任意相邻两数不等，找一个局部最小值位置，要求好于O(N)
比其左右都小就是局部最小
//先判断0位置和n-1位置，有可能直接出结果
//取中点判断，然后不断循环
