二分法三重境界

第一境界：写出不会死循环的二分法

万能模板

public int findPosition(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    
    int start = 0, end = nums.length - 1;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        // 下面的==的情况需要根据题意稍作变化，看是要第一个还是最后一个还是随便一个
        if (nums[mid] == target) {
            end = mid;
        } else if (nums[mid] < target) {
            start = mid; //可以这样偷懒，因为这样也会退出
            // start = mid + 1;
        } else {
            end = mid; //可以这样偷懒，因为这样也会退出
            // end = mid - 1;
        }
    }
    
    if (nums[start] == target) {
        return start;
    }
    if (nums[end] == target) {
        return end;
    }
    return -1;
}

第二境界

有序输入集合中二分法的所有问题OOOXXXX模型，就是左边一个性质，右边一个性质

在排序的数据集上进行二分

在大数组中找target，logn

不知道数组大小，需要倍增来确定目标数组所在的位置

倍增法Exponential Backoff：

场景

• 动态数组

  Vector的扩缩容机制

• 网络重试

public int search(ArrayReader reader, int target) {
    int rangeTotal = 1;
    while (reader.get(rangeTotal - 1) < target) {
        rangeTotal = rangeTotal * 2;
    }
    
    int start = rangeTotal / 2, end = rangeTotal - 1;
    
}

在排序数组中找最接近的k个数

找插入位置+背向双指针

插入位置的话，就找<=target的最右数字，或者>=target的最左数字

找山顶

前单调增、再单调减，找最大值（没有相等，不然会迷失）

public int findPosition(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    
    int start = 0, end = nums.length - 1;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        // 中点比左端点大，则处于上坡的位置，左侧舍弃在右侧找
        if (nums[mid] > nums[mid+1]) {
        //if (nums[mid] > nums[left]) {
            start = mid; //可以这样偷懒，因为这样也会退出
            // start = mid + 1;
        } else {
            end = mid; //可以这样偷懒，因为这样也会退出
            // end = mid - 1;
        }
    }
    
    return Math.max(nums[start], nums[end]);
}

找旋转排序数组的最小值

public int findPosition(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    
    int start = 0, end = nums.length - 1;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        // 中点比左端点大，则处于上坡的位置，左侧舍弃在右侧找
        if (nums[mid] > nums[mid+1]) {
        //if (nums[mid] > nums[left]) {
            start = mid; //可以这样偷懒，因为这样也会退出
            // start = mid + 1;
        } else {
            end = mid; //可以这样偷懒，因为这样也会退出
            // end = mid - 1;
        }
    }
    
    return Math.max(nums[start], nums[end]);
}

logn 次 O(n) 的操作

二分答案 + O(n) 判断答案偏大偏小 二分数组最小长度 x，判断条件是哪个? A: 检测是否存在subarray和 >=k 且长度 = x B: 检测是否存在subarray和 >=k 且长度 <= x