二分法

一个不会出现死循环的通用二分法模板

二分法利用了减治(Decrease and Conquer)的算法思想(Algorithmic Paradigm)，不属于分治(Divide and Conquer)

第一境界

写出不会死循环的二分法

写出不会死循环的二分法
递归与非递归的权衡
二分的三大痛点
通用的二分模板

万能模板

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]);
}

第四境界

在答案集上进行二分
二分答案并验证答案偏大还是偏小

1. 第一步:确定答案范围
2. 第二步:验证答案大小

logn 次 O(n) 的操作

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

求满足某条件的最大值或者最小值

最终结果是个有限的集合

每个结果有一个对应的映射
结果集合跟映射集合正相关或着负相关
可以通过在映射集合上进行二分，从而实现对结果集合的二分

关键词:
Array, 有限可能解, 映射，正负相关, O(NlogN)