数据结构基础之《（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 >> 1
			mid = L + ((R - L) >> 1); // 等于mid = (L + R) / 2
			if (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