认识二分法
原理：
从一个有序数组里面，找中间位置的数（不用时间），判断中间的数和目标数字的大小，目标数字比中间的小，则需要找的范围就在中间位置的左边，直到最后一个数，如果最后一个数都不等于那么不存在这个数。
这是O（log2N)的算法
因为一共砍了log2N次（找中间值的次数），比大小的时间是O（1）。
二分法解决的问题：
在一个有序数组中，找某个数存不存在
在一个有序数组中，找大于某个数的最左位置
比如【1】【2】【3】【3】【3】
找大于等于三的最左位置就是下标为2的位置
在一个有序数组中，找到小于等于某个数的最右位置
局部最小值问题
二分代码：
1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public static boolean exist(int[] sortedArr, int num){
if(sortedArr == null || sortedArr.length == 0){
return false;
}
int L = 0;
int R = sortedArr.length - 1;
int mid = 0;
while(L < R){
mid = L +((R - L) >> 1);
if(sortedArr[mid] == num){
return true;
} else if (sortedArr[mid] > num){
R = mid - 1;
} else {
L = mid + 1;
}
}
return sortedArr[L] == num;
}
|
2.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public static int nearestIndex(int[] arr, int value){
int L = 0;
int R = arr.length - 1;
int index = -1;
while(L <= R){
int mid = L + ((R - L) >> 1);
if(arr[mid] >= value) {
index = mid;
R = mid -1;
} else {
L = mid + 1;
}
}
return index;
}
|
4.在一个无序数组中，任意相邻的数不相等。
什么叫局部最小，就是比如在0位置上的数，比1位置上的数小，那么0位置的数就是局部最小，如果N-1的数比N-2位置的数小那么N=1的数就是局部最小，如果任意 i 位置的数那么要比它左右两边都小那么 i 就是局部最小，一个数组中有很多局部最小只要返回一个就可以了。
原理：
先单独看0位置的数是不是单独最小，如果是直接返回0位置的数，如果不是那么说明0~1位置是一个向下的位置，
再单独看N-1和N-2位置，如果N-1是局部最小如果是直接返回，如果不是那么说明N-2~N-1是上升的，那么在下降和上升中肯定有局部最小的数。
再看中点位置，如果中点位置比左边和右边小那么直接返回中点，如果不成立那么从左边找或者右边小都行，因为一边下降一边上扬，必存在一个点是局部最小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| public static int getLessIndex(int[] arr){
if(arr == null || arr.length == 0){
return -1;
}
if(arr.length == 1 || arr[0] <arr[1]){
return 0;
}
if(arr[arr.length - 1] < arr[arr.length - 2]) {
return arr.length - 1;
}
int left = 1;
int right = arr.length - 2;
int mid = 0;
while(left < right){
mid = (left + right) >> 1;
if(arr[mid] > arr[mid -1]){
right = mid -1;
} else if (arr[mid] > arr[mid +1]) {
left = mid + 1;
} else {
return mid;
}
}
return left;
}
|
