• 通常情况下，二分可以分成索引二分和值域二分
• 索引二分通过二分数组的索引来缩小查找范围，而值域二分通过二分数值范围来缩小查找范围

二分模板

模板1

• 将区间$[l,r]$划分成$[l,mid]$和$[mid+1,r]$

while(l < r){
    int mid = l + r >> 1;
    if(check(mid)) r = mid;
    else l = mid+1;
}

模板2

• 将区间$[l,r]$划分成$[l,mid-1]$和$[mid,r]$

while(l < r){
    int mid = l + r + 1 >> 1;
    if(check(mid)) l = mid;
    else r = mid-1;
}

例题1.寻找重复数字

• 链接：LeetCode287.寻找重复数

思路

• 由抽屉原理可知，n+1长度的数组中数据都处于1到n之间，所以必存在重复元素
• 已经知道了数组的值域为[1,n]，我们可以对值域进行二分：把原数组划分为两个值域区间，然后统计每个区间内数的个数
• 划分区间之后，统计每个区间内的数据个数，并且至少存在一个区间，数的个数大于区间长度
• 如果子区间中，数的个数大于区间长度，则根据抽屉原理，这个区间中必定存在重复元素，继续二分存在重复元素的区间
• 区间长度为1时，重复元素落在该区间内，又因为区间代表值域范围，则找到重复元素

Java代码

class Solution {
    public int findDuplicate(int[] nums) {
        int n = nums.length;
        int l = 1, r = n-1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            int cnt = 0;
            for(int x: nums){
                if(x >= l && x <= mid-1) cnt++;
            }
            if(cnt <= mid-l) l = mid;
            else r = mid-1;
        }
        return l;
    }
}

例题2.有序矩阵中第k小的元素

• 链接：LeetCode378.有序矩阵中第k小的元素

思路

• 矩阵中所有数的值域在区间[matrix[0][0], matrix[n-1][m-1]]之间
• 假设我们二分出来的值为mid，计算$\leq$mid的数有多少个，如果数量$\geq$k，则说明答案的取值为$[l,mid]$，因为第k小的数可能有多个，所以是$\geq$k；如果数量$<$k，说明答案的取值为$[mid+1,r]$，值域缩小到1的时候就是答案，即第k小的数

Java代码

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length, m = matrix[0].length;
        int l = matrix[0][0], r = matrix[n-1][m-1];

        while(l < r){
            int mid = l + r >> 1;
            int i = m-1;
            int cnt = 0;
            for(int j = 0; j < n; j++){
                while(i >= 0 && matrix[j][i] > mid) i--;
                cnt += i+1;
            }
            if(cnt >= k) r = mid;
            else l = mid+1;
        }
        return l;
    }
}