流离之人追逐幻影

用户名：pwj666

访问量：60209

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13957
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

暑三集训--总结
浏览：228

计算1977！*-题解（高精度阶乘）
浏览：1227

蓝桥杯基础练习VIP-阶乘计算-题解(C++代码)
浏览：488

你可能喜欢

寻找右侧边界的二分查找

　　作者: 流离之人追逐幻影　　　　发表时间：2019-08-24 20:05:57 浏览：1021　|　评论：0　

寻找右侧边界的二分搜索
```
int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

while (left < right) {
        int mid = left+(right-left)/ 2;//防溢出
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1; // 注意
}
```
细节改动与影响：
```
改动1:if (nums[mid] == target) {
            left = mid + 1; // 注意
        }
	当 nums[mid] == target 时，不要立即返回，而是增大「搜索区间」的下界 left，使得区间不断向右收缩，达到锁定右侧边界的目的。
```
```
改动2： return left - 1; 
```
比如给二个数组[1,3,4,5,7,9,9,9,16,19]
图解过程：
![](/image_editor_upload/20190824072645_79773.png)
![](/image_editor_upload/20190824072656_24720.png)
![](/image_editor_upload/20190824072706_14814.png)
![](/image_editor_upload/20190824072720_78939.png)
```
由上可知，因为对 left 的更新必须是 left = mid + 1，也就是说while循环结束的时候，nums[left]一定不等于target，nums[left-1]有可能等于target.
所以返回的时候需要将left-1
如果数不存在，则需要打补丁：
.......
if (left == 0) return -1;
return nums[left-1] == target ? (left-1) : -1;
```

总结梳理：
第一个，最基本的二分查找算法：
```
因为我们初始化 right = nums.length - 1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while (left <= right)
同时也决定了 left = mid+1 和 right = mid-1

因为我们只需找到一个 target 的索引即可
所以当 nums[mid] == target 时可以立即返回
```
第二个，寻找左侧边界的二分查找：
```
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid+1 和 right = mid

因为我们需找到 target 的最左侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧右侧边界以锁定左侧边界
```
第三个，寻找右侧边界的二分查找：
```
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid+1 和 right = mid

因为我们需找到 target 的最右侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧左侧边界以锁定右侧边界

又因为收紧左侧边界时必须 left = mid + 1
所以最后无论返回 left 还是 right，必须减一
```

因此在做这类题目的时候，需要注意搜索区间和while的终止条件，有关左右边界的需要注意nums[mid] == target 内部的细节，右侧时需要减一。

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C二级辅导-公约公倍（C语言代码）

C语言训练-尼科彻斯定理（C++代码）

C语言程序设计教程（第三版）课后习题9.1 （C++代码）

寻找右侧边界的二分查找

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

陶陶摘苹果（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

2^k进制数（C++代码）使用递归方法

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

简单的a+b （C语言代码）

1124题解

Tom数（C语言代码）

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C二级辅导-公约公倍 （C语言代码）

C语言训练-尼科彻斯定理 （C++代码）

C语言程序设计教程（第三版）课后习题9.1 （C++代码）

寻找右侧边界的二分查找

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

陶陶摘苹果 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

2^k进制数 （C++代码）使用递归方法

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

简单的a+b （C语言代码）

1124题解

Tom数 （C语言代码）

C二级辅导-公约公倍（C语言代码）

C语言训练-尼科彻斯定理（C++代码）

　　评论区

陶陶摘苹果（C语言代码）

2^k进制数（C++代码）使用递归方法

Tom数（C语言代码）