前言

二分法时间复杂度 O = log(N)

1. 思考！二分法只能建立在有序数组上吗？

经常见到的类型是在一个有序数组上，开展二分搜索但有序真的是所有问题求解时使用二分的必要条件吗?
不
只要能正确构建左右两侧的淘汰逻辑,你就可以二分。
如：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;
		// L..R
		while (L < R) { // L..R 至少两个数的时候
			mid = L + ((R - L) >> 1);//mid = (L + R)/2
			// L + ((R - L) / 2为什么要这样写呢？
			//当 L R都很大时，int类型就可能会溢出
			if (sortedArr[mid] == num) {
				return true;
			} else if (sortedArr[mid] > num) {
				R = mid - 1;
			} else {
				L = mid + 1;
			}
		}
		return sortedArr[L] == num;
	}

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;
            }
        }
        if (index != -1) {
            if (arr[index] != value) {
                index = -1;
            }
        }
        return index;
    }

3)局部最小值问题：返回任意一个局部最小值

正确构建了左右两侧的淘汰逻辑
当arr[mid] > arr[mid - 1]成立，right = mid - 1。淘汰右边的一半
当arr[mid] > arr[mid +1]成立，left = mid + 1; 淘汰左边的一半
二分法：使时间复杂度变成了O(logN)

public static int getLessIndex(int[] arr) {
		if (arr == null || arr.length == 0) {
			return -1; // no exist
		}
		// 数组的开头，如果arr[0] < arr[1] ，arr[0]被定义为局部最小
		if (arr.length == 1 || arr[0] < arr[1]) {
			return 0;
		}
		//数组的结尾，如果arr[N-1] < arr[N-2] ，arr[N-1]被定义为局部最小
		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;
	}