台中市网站建设_网站建设公司_HTML_seo优化

各位好久不见，不知不觉2025都快要结束了，是时候来再总结一次算法（入门）的经验了。

最近笔者看标准算法库时，注意到C++算法库中只有两种二分查找的方法：lower_bound和upper_bound，分别用来查找第一个大于等于某个值的元素和第一个大于某个值的元素。

只有“第一个大于等于”和“第一个大于”，够用吗？

笔者想起了之前关于二分查找题的总结，似乎都是错题总结，而且条理很不清晰，根本没有道出二分查找使用的真相。既然标准库只提供了这俩，说明对于程序员的日常开发来讲，有这两个二分查找是完全够用的。那些之前的技巧和花招只能说是花拳绣腿，可以说都是这两种二分查找的变体。

1、查找第一个大于等于目标值的元素的位置

为了更好的理解二分查找干了什么，我想把这个过程描述为“Left指针要跳过哪些元素”，这是我们写对二分查找的关键。

从我为数不多的算法题经验来看，写二分查找的人分为两派：“Left结果派”和“Update结果派”，Left派习惯在循环结束后让left直接就是所寻找的目标值位置，而Update派习惯在二分过程中不断更新至正确答案。我是觉得Left派更好懂，而且结构清晰，有对称美。

如下，查找第一个大于等于目标值的元素。

int left = 0; int right = size()-1; //left派在left=right时跳出循环 while(right > left){ int mid = (left + right)/2; //什么时候移动left？target在mid的右边 if(target > nums[mid]){ //跳过所有的小于目标值的元素，那最终就是第一个大于等于目标值的元素 left = mid+1; //二分查找法的左指针必须要移动mid+1！ } else{ right = mid; } } return left;

二分查找必须将left移动为mid+1。

如果保持left仅代替mid不移动的话，由于mid向左偏移的特性势必让算法出现死循环的情况（left在right的前一位）。而在(nums[mid]<target)条件下移动至mid+1位置，代表“left要跳过所有小于目标值的元素”，所以最终left只会落在第一个大于等于目标值的元素的位置。

除非是人为将mid的特性改为向右偏移，此时是right必须靠向left来杜绝死循环。

while(right > left){ int mid = (left + right)/2+1; //特性改为向右偏移 //什么时候移动left？target在mid的右边 if(target >= nums[mid]){ left = mid; } else{ right = mid-1; } } return left;

那这个查找到的就是最后一个小于等于目标值的元素，相当于是第一个大于等于目标值元素的左右对称算法。此时我在往期图文已有记载，但我根本记不住！这么麻烦！

但其实最后一个小于等于目标值的位置，就是“第一个大于目标值的位置 - 1）”。根本不用记那么多，只用会写开头说的那两种就好，这就是标准库的高明之处。

2、查找第一个大于目标值的元素的位置

刚刚说了二分查找的关键就是“Left指针要跳过哪些元素”，那查找第一个大于目标值的元素的位置就是“让Left指针跳过所有小于等于目标值的元素”。

如下，查找第一个大于目标值的元素。

int left = 0; int right = size()-1; //left派在left=right时跳出循环 while(right > left){ int mid = (left + right)/2; //什么时候移动left？target在mid的右边 if(target >= nums[mid]){ //跳过所有小于等于目标值的元素，那最终就是第一个大于目标值的元素 left = mid+1; } else{ right = mid; } } return left;

我们观察发现，两种查找的区别只在于Left指针跳跃的条件。仍然是保证了永远是Left指针移动至mid+1，right指针移动至mid。他们之间的不同仅仅在于要跳过的元素特性不同。在(nums[mid]<=target)条件下移动至mid+1位置，就是代表“left要跳过所有小于等于目标值的元素”，那就是第一个大于目标值的元素。

同理，当人为改变特性为向右偏移，是查找最后一个小于目标值的元素。相当于是和第一个大于目标值元素的左右对称算法。

while(right > left){ int mid = (left + right)/2+1; //什么时候移动left？target在mid的右边 if(target > nums[mid]){ left = mid; } else{ right = mid-1; } } return left;

这很麻烦，额外需要记住right往左边跳的情况，还要在二分时加上1，还要right跳到mid-1。所以我们可以直接是找到第一个大于等于目标值的元素位置后减去1，得到最后一个小于目标值的元素。

3、查找最后一个小于目标值的元素的位置

没错就是（第一个大于等于目标值的位置 - 1）。

int left = 0; int right = size()-1; //left派在left=right时跳出循环 while(right > left){ int mid = (left + right)/2; //什么时候移动left？target在mid的右边 if(target > nums[mid]){ //跳过所有的小于目标值的元素，那最终就是第一个大于等于目标值的元素 left = mid+1; //二分查找法的左指针必须要移动mid+1！ } else{ right = mid; } } return left-1;

4、查找最后一个小于等于目标值的元素的位置

没错就是（第一个大于目标值的位置 - 1）。

int left = 0; int right = size()-1; //left派在left=right时跳出循环 while(right > left){ int mid = (left + right)/2; //什么时候移动left？target在mid的右边 if(target >= nums[mid]){ //跳过所有小于等于目标值的元素，那最终就是第一个大于目标值的元素 left = mid+1; } else{ right = mid; } } return left-1;

而上述的几种查找基本上可以覆盖所有常规的二分查找（默认从小到大排序）。

但是需要注意的是，上述情况均没有考虑目标值在数组范围外的情况。如果要考虑目标值在数组范围外的情况，直接用lower_bound或者upper_bound，最终left是数组的左边界或右边界。此时完全可以根据left的位置和left位置的值是否满足条件进行剪枝，可尝试LeetCode.74。

5、总结

综上所述：对于查找第一个大于等于目标值的元素和查找第一个大于目标值的元素只有一个要点——left每次必须跳到mid+1。而其余的两种变体完全可以通过这两种查找减一获得。遇到更复杂的变体只需考虑——我的left要跳过哪些元素，就都可以迎刃而解。

至于两种标准库算法。

1、lower_bound

lower_bound(nums.begin(), nums.begin(), value)

返回第一个大于等于value的元素的迭代器，因为是跳过所有小于目标值的元素，写nums[mid]<target时，left=mid+1。

2、upper_bound

upper_bound(nums.begin(), nums.begin(), value)

返回第一个大于value的元素的迭代器，因为是跳过所有小于等于目标值的元素，写nums[mid]<=target时，left=mid+1。

为啥要叫这两个名字？lower_bound是第一个大于等于，比upper_bound的位置要lower一些，所以叫lower，你细品。

最近事务繁重，时常抽不出身。希望本文能给像我一样的小白一些帮助，祝福各位在2025剩下的时间里事事顺遂。

那么晚安喵~