数据结构基础之《（3）—二分法》

一、认识二分法

1、经常见到的类型是在一个有序数组上，开展二分搜索
2、但有序真的是所有问题求解时使用二分的必要条件吗？不
3、只要能正确构建左右两侧的淘汰逻辑，你就可以二分

二、二分法怎么用

1、在一个有序数组中，找某个数是否存在

	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) {// 左移就是乘以二，右移就是除以二的意思// L 10亿 R 18亿，mid是整数，会溢出// N / 2，一个数除2，就等于这个数二进制形式带符号右移一位 N >> 1mid = L + ((R - L) >> 1); // 等于mid = (L + R) / 2if (sortedArr[mid] == num) {return true;} else if (sortedArr[mid] > num) {R = mid - 1;} else {L = mid + 1;}}return sortedArr[L] == num;}

2、在一个有序数组中，找>=某个数最左侧的位置
例子
12222222333333333344444444444
要找>=2最左侧的位置

	// 在arr上，找满足>=value的最左位置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;}

3、在一个有序数组中，找<=某个数最右侧的位置
4、局部最小值问题
（1）0位置的数比1位置的数小，就是局部最小
（2）N位置的数比N-1位置的数小，就是局部最小
（3）i位置的数，既比i-1位置的数小，也比i+1位置的数小，就是局部最小
5、局部最小问题详解
arr无序数组，任意两个相邻的数都不相等，返回一个局部最小的位置
理解：把值连成一个线，总有高峰低谷

逻辑二分思想：
满足一个条件把另一侧全部排除掉的选项，就可以二分

	public static int getLessIndex(int[] arr) {if (arr == null || arr.length == 0) {return -1; // no exist}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) / 2;if (arr[mid] > arr[mid - 1]) {right = mid - 1;} else if (arr[mid] > arr[mid + 1]) {left = mid + 1;} else {return mid;}}return left;}

三、二分法时间复杂度

1、二分法查找的时间复杂度是依赖于2的几次方，所以O是log2(N)，以2为底可以直接写成logN