算法学习-二分模板

本文最后更新于：April 5, 2022 am

纸上得来终觉浅，绝知此事要躬行。路漫漫其修远兮，吾将上下而求索！知识是经过历史的巨人沉淀下来的，别总想着自己能够快速学会，多花点时间去看看，也许会发现些不同的东西。你能快速学会的、觉得简单的东西，对于别人来说也是一样的。人外有人，天外有天。当努力到达了一定的程度，幸运自会与你不期而遇。

目录

二分查找经典模板

1
2
3
4
5
6
7
8
9
public int search(int left,int right,int[] nums, int target) {
  while (left <= right) {
    int mid = left + ((right - left) >> 1);
    if (nums[mid] == target) return mid;
    else if (nums[mid] > target) right = mid - 1;
    else left = mid + 1;
  }
  return -1;
}

整数二分

版本一

将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1，计算mid时不需要加1。

1
2
3
4
5
6
7
8
9
int bsearch_1(int l, int r){
    while (l < r){
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

版本二

将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid，此时为了防止死循环，计算mid时需要加1。

1
2
3
4
5
6
7
8
int bsearch_2(int l, int r){
    while (l < r){
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

浮点数二分

1
2
3
4
5
6
7
8
9
10
11
bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r){
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps){
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

应用

第一个等于的下标

返回查找到的数的下标，没有找到则返回 -1。其中，left 和 right 是有效的范围下标。

1
2
3
4
5
6
7
8
9
public static int search(int left,int right,int[] nums, int target) {
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
}

JavaAPI

1
Arrays.binarySearch(int[],fromIndex,toIndex,value);

若找不到则返回负数，而不是 -1 。还需要注意的是，数组中若有多个待查值，则不确定找到的是哪一个。

最后一个等于的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private static int search2(int left,int right,int[] a, int value) {
        int n = right; //最后的一个位置下标
        while (left <= right){
            //中间下标
            int mid = left + ((right - left) >> 1);
            if (a[mid] > value){
                right = mid - 1;
            }else if (a[mid] < value){
                left = mid + 1;
            }else {
                //当该元素为最后一个元素或该元素后一个值不跟其相等则为最后一个符合条件
                if (mid == n || a[mid + 1] != value){
                    return mid;
                }else {
                    //从小到大第一个则左下标向右移
                    left = mid + 1;
                }
            }
        }
        return -1;
}

第一个大于的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static int search6(int left , int right ,int[] a, int value) {
        int n = right; //记录最后一个数据的下标
        while (left <= right) {
            int mid=left+(right-left)/2;
            if (a[mid] <= value){  //关键点，<=
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        if(left>n)     //区分索引越界，即没找到,范围为1~n的写>n；范围是0~n-1写≥n.n表示最后的一个数据下标
            return -1;
        return left;
}

第一个大于等于的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static int search3(int left , int right ,int[] a, int value) {
        while (left <= right){
            //中间下标
            int mid = left + ((right - left) >> 1);
            if (a[mid] >= value){
                //当该元素为第一个元素或该元素前一个值小于给定值则为第一个符合条件
                if (mid == 0 || a[mid - 1] < value){
                    return mid;
                }else {
                    //从小到大第一个则右下标向左移
                    right = mid - 1;
                }
            }else {
                left = mid + 1;
            }
        }
        return -1;
}

最后一个小于的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static int search5(int left , int right ,int[] a, int value) {
        while (left <= right) {
            int mid=left+(right-left)/2;
            if (a[mid] >= value){  //关键点，>=
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        if(right<0)     //区分索引越界，即没找到
            return -1;
        return right;
}

最后一个小于等于的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static int search4(int left , int right ,int[] a, int value) {
        int n = right;
        while (left <= right){
            //中间下标
            int mid = left + ((right - left) >> 1);
            if (a[mid] > value){
                right = mid - 1;
            }else {
                //当该元素为最后一个元素或该元素后一个值大于给定值则为最后一个符合条件
                if (mid == n || a[mid + 1] > value){
                    return mid;
                }else {
                    //从小到大第一个则左下标向右移
                    left = mid + 1;
                }
            }
        }
        return -1;
}