基础二分模板

有单调性的题目一定可以二分 但没有单调性不一定不可以二分
另外 最大值最小 最小值最大 –> 二分

二分

闭区间写法 [l,r]

推荐这一种 最好记 最不容易出错
闭区间就是在 定义初始l r的时候 l与r 都是直接取区间上的位置
即 l = 0 , r = n - 1

对应代码 返回相等的数 前面的一个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 相同找最前面的 
// 闭区间 写法 
public int binary1(int [] arr, int x){
    int n = arr.length;
    // l 与 r 直接取区间内的位置
    int l = 0 , r = n - 1; 
    // l始终指向左半部分区域 r始终指向右半区域
    // 在闭区间上操作 所以 l与r始终应该是指向区间内的元素
    // 所以应该是 l<=r 即只要区间不为空那么就继续循环 
    while(l <= r){
        // left+(right - left) // 2     防溢出写法
        int mid = l + r >> 1;
        // arr[mid] >= x
        // 则代表 mid + 1 到 r 这一段区间与x的关系是已经确定的
        //   (l x mid r ) 所以更新 r -> (r = mid - 1) -> l x r
        if(arr[mid] >= x){
            // 即接下来要寻找的是  
            // [left,mid - 1]
            r = mid - 1;
        }else{
            // 即需要找的是[mid + 1,right]
            // l mid x r -> 更新 l > l x r 
            // 由于始终是在闭区间操作 所以l = mid
            l = mid + 1;
        }
    }
    return l;
}

开区间写法 左闭右开[l,r)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 相同的找最前面的
// 开区间写法 左闭右开 [l,r)
public int binary1(int [] arr,int x){
    int n = arr.length;
    // 右开 即右指针始终指向数组边界外
    int l = 0 , r = n;
    // 左闭右开 所以当 左右相等时证明区间为空 则退出循环
    while(l < r){
        int mid = l + r >> 1;
        if(arr[mid] >= x){
            // l x mid r
            // 所以下一步需要寻找的区间在 [l,mid - 1) 右开 所以r=mid 而不是mid - 1
            r = mid;
        }else{
            // l mid x  r
            // 下一步需要寻找的是 [mid + 1, r)
            l = mid + 1; 
        }
    }    return l;
}

开区间 左右都开 (l,r)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 相同的找最前面的
// 开区间写法 左右都开 (l,r)
public int binary1(int [] arr,int x){
    int n = arr.length;
    // 左右都开 即左右指针都不指向区间内
    // 所以 l = - 1 ,  r = n
    int l = -1 , r = n;
    // 左右指针都不指向区间内
    // 所以当l  + 1 = r时 意味着区间为空
    while(l + 1 < r){
        int mid = (l + r) >> 1;
        
        if(arr[mid] >= x){
            // l mid r -> l x mid r
            // (l,mid - 1)
            r = mid;
        }else{
            // l mid r -> l mid x r
            // (mid + 1, r)
            l = mid;
        }
    }
    if(r >= n || arr[r] != x){
        return -1;
    }
    return r;
}

>= 转换为其他形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
1. ```>= x``` 转换为 > x  即 ```>= x + 1```
2. ```>= x``` 转换为 < x  即 ```(>=x) - 1```
3. ```>= x``` 转换为 <= x 即 ```(>x)  - 1```  -> ```>= x + 1``` - 1


## 例题

### leetcode 34 在排序数组中查找元素的第一个和最后一个位置

原题链接:
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

```java

/**
查找元素x的第一个位置和最后一个位置 即
1.>=x 的第一个位置
2.>=(x + 1) 的第一个位置前面的的一个位置

 */
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int a = lower_bound(nums,target);
        if(a >= nums.length || nums[a] != target){
            return new int [] {-1,-1};
        }

        int b = lower_bound(nums,target + 1) - 1;
        // a 存在那么b一定存在 因为大不了 a == b
        return new int [] {a,b};
    }

    // >= 
    // 闭区间写法 [l,r]
    public int lower_bound(int [] arr, int x){
        int l = 0 , r = arr.length - 1;
        while(l <= r){
            int mid = l + r >>1;
            if(arr[mid] >= x){
                // l x mid r
                // [l , mid - 1]
                r = mid - 1;
            }else{
                // l mid x r
                // [mid + 1 , r]
                l = mid + 1;
            }
        }

        return l;
    }
}

leetcode 162 寻找峰值

原题链接:
https://leetcode.cn/problems/find-peak-element/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int findPeakElement(int[] nums) {
        // 使用lower_bound 的闭区间写法
        int n = nums.length;
        int l = 0 , r = n - 2;
        while(l <= r){
            int mid = (l + r) >> 1;
            // 证明 mid 要么是峰顶 或者 峰顶 在左侧
            // mid mid + 1 r
            // 即查找区间更新为[l , mid - 1]
            if(nums[mid] >= nums[mid + 1]){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }

        return l;   
    }
}

leetcode 153 寻找旋转排序数组中的最小值

原题链接:
https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
    旋转一次的意思 最后一个元素往前置
    所以旋转后必定是分为 两段递增的序列

    每次二分mid与最后一个元素x比较  
    mid >= x 即 l x mid r  证明该段序列位于最小值的右边 否则 证明mid 是最小值 或者在mid左边是最小值
 */

class Solution {
    public int findMin(int[] nums) {
        int k = lower_bound(nums);
        return nums[k];
    }

    public int lower_bound(int [] arr){
        int n = arr.length;
        int l = 0 , r = n - 2;
        int last = arr[n - 1];
        while(l <= r){
            int mid = l + r >> 1;
            // l mid x  r 
            if(arr[mid] >= last){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }

        return l;
    }
}

33 搜索旋转排序数组

法1: 直接二分 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
    双重判断 还是与最后一个数last 比较 
    记录要寻找的数为 x   x > last  则证明存在x  
    而如果mid >= x  则证明x 位于 l mid 这一段
    否则 x 位于 mid + 1 , r 这一段
 */
class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        // n - 1 为last 不加入 比较
        int l = 0 , r = n - 2;
        while(l <= r){
            int mid = l + r >> 1;
            if(check(nums,target,mid)){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }

        if(l >= n || nums[l] != target){
            return -1;
        }

        return l;
    }

    public boolean check(int [] arr,int target , int mid){
        int last = arr[arr.length - 1];
        // mid >= last 
        // mid 此时处于last 右边 l last mid r
        // r = mid - 1
        if(arr[mid] >=  last){
            // target 与 mid 属于 同区间
            // l (last) mid r last
            // l target mid r last
            // 即可以确定mid 右边为另外一种性质的序列 且target与mid处于同种性质的序列中
            return target > last && arr[mid] >=  target;
        }else{
            //  l mid last r
            //  如果target > last   l mid (last)  target r  因为是有序递增的 证明 target处于第一个有序递增区间 即mid 的右边是另外一种性质的序列 
            //  如果 arr[mid] >= target
            // l target mid (last)  r  则证明mid target均属于第一个有序递增区间 即mid 右半部分为另外一种性质序列 
            return target > last || arr[mid] >= target;
        }
    }
}

leetcode35 搜索插入位置

原题链接:
https://leetcode.cn/problems/search-insert-position/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int searchInsert(int[] nums, int target) {
        // 练习一下 开区间写法
        int n = nums.length;
        int l = - 1 , r = n;
        while(l + 1  < r){
            int mid = l + r >> 1;
            if(nums[mid] >= target){
                r = mid;                
            }else{
                l = mid;
            }
        }

        return r;
    }
}

leetcode 209 长度最小的子数组

原题链接:
https://leetcode.cn/problems/minimum-size-subarray-sum/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/** 
    前缀和 + 二分
*/
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int [] sum = new int [n + 1];
        // 前缀和数组 
        for(int i = 1 ; i <= n ; i++){
            sum[i] = sum[i - 1] + nums[i - 1];
        }

        int ans = n + 10;

        // 遍历 nums 的右端点i 寻找满足 sum[i - mid] = sum[i] - sum[mid] >= target  条件的 mid的最小值
        // 即 sum[i] - target >= sum[mid] 
        for(int i = 1 ; i <= n ; i++){
            // sum[i] 表示 nums[0] ... nums[i - 1]的加和
            int d = sum[i] - target;
            int l = 0 , r = i + 1;
            while(l + 1 < r){
                int mid = l + r >> 1;
                // l mid d  r 
                // r 应该是返回的 sum[r] >= d 的第一个位置
                // 所以要求 sum[r] <= d 即 sum[r] > d 的第一个位置的前一个位置 即 sum[r] >= d + 1 的前一个位置
                // d <= sum[mid]
                // l x mid r
                if(sum[mid] >= d + 1){
                    r = mid;
                }else{
                    l = mid;
                }
            }

            // 如果存在答案 
            // r == 0 表示 该数已经在区间外了 肯定不是答案

            if(r > 0 && r <  i + 1 && sum[r - 1] <=  d){
                // r = r - 1;
                // r - 1是答案的位置 即 sum[i] - sum[r - 1] 为所求子数组
                // 其元素为 nums[r] , nums[r + 1] , nums[r + 2] , ... , nums[i] 为 i - r + 1个数  
                ans = Math.min(ans,i - r + 1);
            }
        } 

        return ans == n + 10 ? 0 : ans ;
    }
}

leetcode 240 搜索二维矩阵 II

原题链接:
https://leetcode.cn/problems/search-a-2d-matrix-ii/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 抽象BST
        // 右上角为根 向左为左子树 向下为右子树
        int n = matrix.length, m = matrix[0].length;
        int x = 0 , y = m - 1;
        while(x < n && y >= 0 && matrix[x][y] != target){
            if(matrix[x][y] > target){
                y--;
            }else{
                x++;
            }
        }

        if(x >= n || y < 0  || matrix[x][y] != target){
            return false;
        }

        return true;
    }
}

leetcode 278 第一个错误的版本

原题链接:
https://leetcode.cn/problems/first-bad-version/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        // 这题刚好会溢出到爆int那一位 用这种闭区间的写法 会好一些
        int l = 1 ,  r = n;
        while(l <= r){
            long tmp = (long)  l + r  >> 1;
            int mid = (int)tmp;
            // 所有版本出错的第一个错误 
            // 即 >= 
            // l x  mid  r 
            if(isBadVersion(mid)){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }

        return l;
    }
}


leetcode 69 x 的平方根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int mySqrt(int x) {
        int l = 0, r = x;

        while(l <= r){
            long mid = l + r >> 1;
            long tmp = mid * mid;
            if(tmp >= x){
                r = (int)mid - 1;
            }else{
                l = (int)mid + 1;
            }
        }   


        // 这里因为返回的时第一个大于等于的值 但答案有可能是位于 [x,x + 1]
        if(l * l >= x + 1){
            l--;
        }

        return l;
    }
}

Acwing旧模板 不推荐使用 整数二分 边界情况

二分一共两个模板 适用于两种不同的情况

  1. 版本1
    满足check()区间内找左边界 -> 将区间划分为 [l,mid] 和 [mid + 1, r] 时
    其每次操作都将 r = mid 或者 l = mid + 1 , 计算mid时不需要加1 (可以看r r不加1 那么 mid就不加1)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    binary_search(int x){
        while(l < r){
            int mid = l + r >> 1;
            if(check(x)){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }

  2. 版本2
    满足check()区间内找右边界 -> 将区间划分为 [l,mid - 1] 和 [mid,r]
    其每次操作都将 r = mid - 1或 l = mid , 为了防止死循环 计算时要将mid + 1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    binary_search(int x){
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(check(x)){
                l = mid;
            }else{
                r = mid - 1;
            }
        }

        return l;
    }

c++ 二分库函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/*
    lower_bound 返回 第一个大于等于 x 的位置 
    (也就是当查询到多个等于x的数时 返回前面那个)
*/
vector<int>q;
int low = lower_bound(q.begin(),q.end(),x) - q.begin();
// 得到对应的数
cout << q[low] << endl;

/*
    这里注意 如果想要返回多个等于x的数 后面的那个
    不能直接用下面的upper_bound 而应该对lower_bound 进行转化
    如下
*/
// 返回第一个大于 x 的数 的第一个位置的前面一个位置 即多个等于x的数中 最后面那个数
    low = lower_bound(q.begin(),q.end(),x + 1) - q.begin() - 1;

/*
    upper_bound 返回 第一个大于x的位置
*/
int upp = upper_bound(q.begin(),q.end(),x) - q.begin();
cout << q[upp] << endl;

四种二分求有序数组 类型的转换 (以Golang为例)

有序数组的二分一共就四种类型:

= > < <=
最常见的类型是 >= 例如go的内置二分函数就是求的>=
(>=问题:即 返回有序数组中第一个 >= x 的数的位置 如果所有数都 < x 返回数组长度)
但是这四种类型的求解都可以在 >= 的形式基础上进行转换
记 要二分查找的这个数为x

  1. 大于 > -> >= x + 1 大于等于x+1这个数
  2. 小于 < -> (>= x) - 1 大于等于x左边的一个数
  3. 小于等于 <= -> ( > x) - 1 大于x左边的一个数 即 大于等于x+1左边的一个数

例题总结

二分本身这个点比较简单 但可以和其他很多形式的题目进行结合
经典例题总结
难度值:1 对于模板的基本应用
数的范围
难度值:2 结合一些基本场景
二叉搜索树最近节点查询
难度值3:结合场景 且思维难度较高
袋子里最少数目的球

数的范围

原题链接:
https://www.acwing.com/problem/content/791/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
using namespace std;

const int N = 1e5 + 10;
int a[N];
int n,q;

int main(){
    cin>>n>>q;
    for(int i = 0 ; i < n ; i++){
        cin>>a[i];
    }
    int ans[2];
    int l,r;    
    while(q--){
        int k;
        cin >> k;
        // 寻找最左边的点 即符合check() 找左边界
        l = 0;
        r = n - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(a[mid] >= k){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        
        // 没找到的情况
        if(a[l] != k){
            cout<< "-1 -1"<<endl;
            continue;
        }
        
        ans[0] = l;
        
        l = 0;
        r = n - 1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(a[mid] <= k){
                l = mid;
            }else{
                r = mid - 1;
            }
        }
        ans[1] = l;
        for(int i = 0 ; i < 2;i++){
            cout<<ans[i]<<' ';
        }
        cout<<endl;
    }
}

二叉搜索树最近节点查询

原题链接:
https://leetcode.cn/problems/closest-nodes-queries-in-a-binary-search-tree/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *`     Right *TreeNode
 * }
 */
func closestNodes(root *TreeNode, queries []int) [][]int {
    var inorder func(root *TreeNode)
    q := []int{}
    inorder = func(root *TreeNode){
        if root == nil {
            return 
        }
        inorder(root.Left)
        q = append(q,root.Val)
        inorder(root.Right)
    }
    
    inorder(root)
    
    ans := [][]int{}
    for _,v := range queries{
        a := sort.SearchInts(q,v + 1) - 1
        b := sort.SearchInts(q,v)
        if a >= len(q) || a < 0{
            a = -1
        }else{
            a = q[a]
            if a > v{
                a = -1
            }
        }
        
        if b >= len(q) {
            b = -1
        }else{
            b = q[b]
            if b < v {
                b = -1
            }
        }

        ans = append(ans,[]int{a,b})
    }

    return ans 
}

袋子里最少数目的球

原题链接:
https://leetcode.cn/problems/minimum-limit-of-balls-in-a-bag/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
    最大值最小 ---> 二分
    二分最大值 
    l = 0 , r = 最大值 
    经过op次操作 将最大值分摊给其他数 从而达成mid 当op <= maxOperations 为符合条件 则继续向左区间寻找(最小化最大值)
    即check() 符合条件的在左区间 
*/
class Solution {
public:
    bool check(int m,int maxOperations,vector<int>&nums){
        // m = 0 时  ops为无穷大 肯定是大于maxOperations 不符合条件
        if(m == 0){
            return false;
        }
        int ops = 0;
        for(auto & x : nums){
            // 如果当前值超过了 所设定的最大值
            // 则其差距需要 (x - 1)/m 次操作进行弥补  
            // m - 1 下取整 
            ops += (x - 1)/ m;
        }
        if(ops <= maxOperations){
            return true;
        }
        return false;
    }

    int minimumSize(vector<int>& nums, int maxOperations) {
        int l = 0 , r = *max_element(nums.begin(),nums.end());
        while(l < r){
            int mid = l + r >> 1;
            if(check(mid,maxOperations,nums)){
                r = mid;
            }else{
                l = mid + 1;
            }
        }

        return l;
    }
};