仰望星空

位我上者，灿烂星空；道德律令，在我心中。

0%

二分查找左右边界

发表于 更新于 分类于 ，
本文字数： 2.1k 阅读时长 ≈ 2 分钟

【道德经·第四章】道冲而用之或不盈，渊兮似万物之宗。挫其锐，解其纷，和其光，同其尘。 湛兮似或存，吾不知谁之子，象帝之先。

基本的二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int BinarySearch(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;  // 注意

    while(left <= right) {
        int mid = left + (right-left)/2;
        if(nums[mid] == target)
            return mid;
        else if(nums[mid] < target)
            left = mid+1;
        else if(nums[mid] > target)
            right = 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
int left_bound(vector<int>& nums, int target) {
    // 搜索区间为[left, right]
    int left = 0, right = nums.size()-1;  
    while(left <= right) {
        int mid = left + (right-left)/2;
        if(nums[mid] < target) {
            // 搜索区间变为[mid+1, right]
            left = mid+1; 
        } else if(nums[mid] > target) {
            // 搜索区间变为[left, mid-1]
            right = mid-1;
        } else if(nums[mid] == target) {
            // 别返回，收缩右边界，锁定左边界
            right = mid-1;
        }
    }  // 循环结束条件：left=right+1

    if(left>=nums.size() || nums[left]!=target)
        return -1;

    return left;
}

寻找右侧边界的二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int right_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size()-1;
    while(left <= right) {
        int mid = left + (right-left)/2;
        if(nums[mid] < target) {
            // 搜索区间变为[mid+1, right]
            left = mid+1;
        } else if(nums[mid] > target) {
            // 搜索区间变为[left, mid-1]
            right = mid-1;
        } else if(nums[mid] == target) {
            // 别返回，收缩左侧边界，锁定右侧边界
            left = mid+1;
        }
    }

    if(right<0 || nums[right]!=target)
        return -1;
    
    return right;
}

查找第一个不小于目标值的数（lower_bound）

比如在数组 [2, 4, 5, 6, 9] 中查找数字3，就会返回数字4的位置；在数组 [0, 1, 1, 1, 1] 中查找数字1，就会返回第一个数字1的位置。可变形为查找最后一个小于目标值的数（返回改为right-1）。

1
2
3
4
5
6
7
8
9
int find(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) left = mid+1;
        else right = mid;
    }
    return right;
}

查找第一个大于目标值的数（upper_bound)

比如在数组 [2, 4, 5, 6, 9] 中查找数字3，还是返回数字4的位置；在数组 [0, 1, 1, 1, 1] 中查找数字1，就会返回坐标5，通过对比返回的坐标和数组的长度，我们就知道是否存在这样一个大于目标值的数。可变形为查找最后一个不大于目标值的数（返改为回right-1）。

1
2
3
4
5
6
7
8
9
int find(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) left = mid+1;
        else right = mid;
    }
    return right;
}

位我上者，灿烂星空；道德律令，在我心中。