Consolexin's blog
consolexinhun
2021-11-13
目录

二分下标

# 概念

就是在有序数组中以 O(logn) 的复杂度找到目标元素

警告

前提是数组是有序的，或者是部分有序的（旋转有序数组或者山脉数组）

# 左闭右开写法

个人比较喜欢这种方式

# 寻找指定元素

找到某个指定元素，如果不存在，返回-1

class Solution {
public:
    int search(vector<int>& nums, int target) {
      int n = nums.size();
      int l = 0, r = n;
      while(l < r){
        int mid = l + (r-l)/2;
        if(nums[mid] < target){
          l = mid+1;
        }else if(nums[mid] == target){
          return mid;
        }else{
          r = mid;
        }
      }
      return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

需要注意的有几点，while 中的条件，mid 取值防溢出， 退出循环时 left 和 right 的相对关系

笔记

l = 0, r = n

在初始化时，left 为数组第一个元素，right 为数组末尾，但是取不到 right，也就是搜索的区间为 [left, right)

while(l < r)

如果 left = right，也就是搜索的区间为空了，因此 while 循环退出的条件是 left = right

if(nums[mid] > target) right = mid

当发现中间的值比 target 要大，应该压缩右边界，由于 right 取不到，所以 right 可以等于 mid（已经确认mid的元素要大于 target 了）

# 找到数组中第一个不小于 target 的

找不到返回-1

也就是 lower_bound 的实现，不过 lower_bound 找不到会返回末尾的迭代器（也就是所有元素都比 target 小）

其实就是target第一次出现的位置

退出循环时有以下几种情况

当所有元素都比 target 小，那么 left 会一直增加到 n

当所有元素都比 target 大，那么 right 会一直减到 0

int my_lower_bound(vector<int>&v, int target){
    int n = v.size();
    int l = 0, r = n;

    while(l < r){
        int mid = l + (r-l)/2;
        if(v[mid] < target) l = mid+1;
        else if(v[mid] > target) r = mid;
        else{  // 由于要找到第一个不小于target的，因此在相等时应该压缩右边界
            r = mid;
        }
    }

    if(l == n || v[l] != target) return -1;
    return l;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 找到数组中最后一个不小于 target 的

找不到返回-1

也就是 upper_bound 找到的位置减1，upper_bound 是找到数组中第一个大于 target 的，不过 upper_bound 找不到 target 时会返回末尾迭代器（所有元素都比 target 小）

其实就是 target 最后一次出现的位置

int my_upper_bound(vector<int>&v, int target){
    int n = v.size();
    int l = 0, r = n;
    while(l < r){
        int mid = l + (r-l)/2;
        if(v[mid] < target) l = mid+1;
        else if(v[mid] > target) r = mid;
        else{  // 在相等时候，应该压缩左边界
            l = mid+1;
        }
    }

    // 返回的l是第一个比target大的, l-1是最后一个小于等于target的
    if(l == 0 || v[l-1] != target) return -1;  // 所有元素都比target大，那么 l=r=0
    return l-1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 两端闭写法

# 寻找指定元素

找到某个指定元素，如果不存在，返回-1

class Solution {
public:
    int search(vector<int>& nums, int target) {
      int n = nums.size();
      int l = 0, r = n-1;
      while(l <= r){
        int mid = l + (r-l)/2;
        if(nums[mid] < target){
          l = mid+1;
        }else if(nums[mid] == target){
          return mid;
        }else{
          r = mid-1;
        }
      }
      return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

需要注意的有几点，while 中的条件，mid 取值防溢出， 退出循环时 left 和 right 的相对关系

笔记

l = 0, r = n-1

在初始化时，left 为数组第一个元素，right 为数组最后一个元素，也就是搜索的区间为 [left, right]

while(l <= r)

如果 left = right+1，也就是搜索的区间为空了，因此 while 循环退出的条件是 left = right+1

if(nums[mid] > target) right = mid-1

当发现中间的值比 target 要大，应该压缩右边界，mid 已经大于 target 了，左边的元素是 mid-1，那么 right=mid-1

# 找 target 第一次出现的位置

int mylow_bound(vector<int>&v, int target){
    int n = v.size();
    int l = 0, r = n-1; 
    while(l <= r){  // 退出循环时 left = right+1
        int mid = l + (r-l)/2;
        if(v[mid] < target)
            l = mid+1;
        else if(v[mid] > target)
            r = mid - 1;
        else  // 在相等的时候，压缩右边界
            r = mid - 1;
    }
    if(l == n || v[l] != target) return -1;
    // 也可以写成 if(r+1 == n || v[r+1] != target) return -1; return r+1;
    return l;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 找 target 最后一次出现的位置

int myup_bound(vector<int>&v, int target){
    int n = v.size();
    int l = 0, r = n-1;
    while(l <= r){  // 退出循环时 left = right+1
        int mid = l + (r-l)/2;
        if(v[mid] < target) {
            l = mid+1;
        }else if(v[mid] > target){
            r = mid-1;
        }else{  // 相等时，压缩左边界
            l = mid+1;
        }
    }

    // 在相等时 l=mid+1，那么left一定是大于target的数，因此right小于等于target
    if(r == -1 || v[r] != target) return -1;
    return r;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 题目

# LC 33. 搜索旋转排序数组

https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

主要就是mid 和右边的比较，利用有序性，比较 mid 和 right 的大小

如果 mid 大于 right 说明 左边（left，mid）是有序的
    如果 target 在 left到mid 中，收缩右边界
    否则收缩左边界
mid 小于 right 说明右边（mid，right）是有序的
    如果 target 在 mid 到 right中，收缩左边界
    否则收缩右边界
1
2
3
4
5
6
class Solution {
public:
    int search(vector<int>& nums, int target) {
        
        int l = 0, r = nums.size()-1;
        while(l <= r){
            int mid = l + (r-l)/2;
            if (nums[mid] == target) return mid;


            if(nums[mid] < nums[r]){ // 右边是有序的
                if(nums[mid] <= target && target <= nums[r]){  // 在右边，收缩左区间
                    l = mid+1;
                }else{
                    r = mid-1;
                }
            }else{// 左边是有序的
                if(nums[l] <= target && target <= nums[mid]){ // 是否在左边
                    r = mid-1;
                }else{
                    l = mid+1;
                }
            }
        }
        return -1;
    }
};
// 常错样例
// [3,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

注意

那么为什么不与左边的比呢？ 因为 mid = l + (r-l)/2 如果只有两个元素，那么中间的元素和左边的一样，因此不能保证中间到右边的有序性

所以可以 mid = l + (r-l+1)/2，使得左边的和中间的元素不一样

精髓 int mid = l + (r-l+1)/2;
如果mid 小于 左边的，说明右边mid到right是有序的
    if target 在mid到right，那么收缩左边界
    否则收缩右边界 
mid 大于左边的，说明左边left到mid是有序的
    if target 在left到mid，那么收缩右边界
    否则收缩左边界
1
2
3
4
5
6
7
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n-1;
        while(l <= r){
            int mid = l + (r-l+1)/2;  // 注意这里，只有2个元素时,mid和left会重合，
            if(nums[mid] == target) return mid;

            else if(nums[mid] < nums[l]){// mid 到 right 是有序的
                if(nums[mid] < target && target <= nums[r]){
                    l = mid+1;
                }else{
                    r = mid-1;
                }
            }else{ // left 到 mid 是有序的
                if(nums[l] <= target && target < nums[mid]){
                    r = mid-1;
                }else{
                    l = mid+1;
                }
            }
        }

        return -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

# LC 81. 搜索旋转排序数组 II

https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/

与上一题的区别是存在重复的数字 那么可能存在 mid 和 right 相等的情况，相等时压缩 right

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n-1;
        while(l <= r){
            int mid = l + (r-l)/2;
            if(nums[mid] == target) return true;

            else if(nums[mid] > nums[r]){ // left 到 mid 必然有序
                if(nums[l] <= target && target < nums[mid]){
                    r = mid-1;
                }else{
                    l = mid+1;
                }
            }
            else if(nums[mid] < nums[r]){ // mid 到right 有序
                if(nums[mid] < target && target <= nums[r]){
                    l = mid+1;
                }else{
                    r = mid-1;
                }
            }else{  // 注意这里，相当于去重了，因为中间的和右边相等，中间不等于target，那么右边也不等于target
                r--;
            }
        }

        return false;
    }
};
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

# LC 153. 寻找旋转排序数组中的最小值

https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/

mid 与 右边比较

如果mid 大于右边，那么 left 到 mid 有序，解在右边 mid+1 到 right
    left = mid+1
mid 小于右边，那么 left 到 mid 有序，解在左边，left 到 mid
    right = mid （注意这样会死循环，所以特判 right 是否和 mid 相等，相等说明只有一个元素了）
1
2
3
4
class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n-1;

        while(l <= r){
            int mid = l + (r-l)/2;
            if(nums[mid] < nums[r]){
                r = mid;
            }else if(nums[mid] > nums[r]){
                l = mid+1;
            }else{ // mid = r
                return nums[mid];
            }
        }
        return nums[l];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# LC 154. 寻找旋转排序数组中的最小值 II

https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

有重复元素，当中间和右边的相等，压缩右边的区间就行了

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n-1;

        while(l <= r){
            int mid = l + (r-l)/2;
            if(nums[mid] < nums[r]){
                r = mid;
            }else if(nums[mid] > nums[r]){
                l = mid+1;
            }else{
                r--;
            }
        }
        return nums[l];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

甚至可以直接交到上一题上

# LC 275. H 指数 II

https://leetcode-cn.com/problems/h-index-ii/

l, r 只表示数组下标，n-l 才表示引文数量

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int l = 0, r = n;
        while(l < r){
            int mid = l + (r-l)/2;
            // n-mid 表示大于等于mid的论文数
            if(citations[mid] > n-mid){ // 说明是不满足要求的，应该减小mid
                r = mid;
            }else if(citations[mid] < n-mid){
                l = mid+1;
            }else{ // 相等时，尽可能扩大引文数量，也就是减小数组的值
                r = mid;
            }
        }
        return n-l;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# LC 852. 山脉数组的峰顶索引

https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/

mid 与左右两边比较 比左右两边大，就是它 比左边小，在山峰右边，峰值在左边 比右边小，在山峰左边，峰值在右边

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int n = arr.size();
        int l = 0, r = n-1;
        while(l <= r){
            int mid = l + (r-l)/2;
            if(arr[mid-1] < arr[mid] && arr[mid] > arr[mid+1]) return mid;
            else if(arr[mid-1] > arr[mid] ){ // 峰值在左边
                r = mid;
            }else{ // 峰值在右边
                l = mid;
            }
        }
        return l;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
编辑 (opens new window)
上次更新: 2025/05/21, 06:42:57
多重背包
二分答案

← 二分答案→

最近更新
01
6-其他操作
05-20
02
4-联结
05-20
03
7-管理
05-20
更多文章>
Theme by Vdoing | Copyright © 2019-2025 Consolexinhun | MIT License
×