C++ 二分查找upper_bound lower_bound算法实现+习题博客

ゝ一世哀愁。 2022-09-13 04:08 80阅读 0赞

### 文章目录 ###

*   *  前引
     *  upper\_bound lower\_bound算法理解
     *  my\_upper\_bound代码实现
     *  my\_lower\_bound代码实现
     *  相关习题博客链接 自写upper\_bound lower\_bound函数

--------------------

## 前引 ##

--------------------

**这部分今天在刷力扣专题的时候 就想到了自己实现`upper_bound` 和 `lower_bound`函数 我记得大概在几个月以前自己就去搜过 那个时候自己依葫芦画瓢自己写了 但是觉得不是属于自己的 之后还需要自己写一遍**

**于是今天就来了 刚好遇到了需要使用`lower_bound` `upper_bound`的习题 就不用库函数了 自己写一个 当然返回的值不是`iterator`啦 是在数组中的位置**

--------------------

## upper\_bound lower\_bound算法理解 ##

--------------------

**对于`upper_bound`的话 函数值是返回第一个大于`target`的位置**  
**对于`lower_bound`的话 函数值是返回第一个大于等于`target`的位置 如果数组中有`target`的话 就返回第一个`target`的位置 没有的话返回第一个大于`target`的位置**

**对于这两个函数 我们只需要把二分查找稍微修改一下即可 对于`left` `right`两边两个指针 我们移动位置判定条件不一样**  
**详细的话看下面代码就行了**

--------------------

## my\_upper\_bound代码实现 ##

--------------------

int my_upper_bound(vector<int>& nums,int target)
        { 
            int left = 0,right = nums.size();
            while(left < right)
            { 
                int mid = (left + right)/2;
                // 如果mid 小于或者等于 left即移位 
                // 只要每次低位或者高位指针会移动 则不会存在无限循环的情况
                if(nums[mid] <= target) left = mid + 1;       
                else right = mid; 
            }
            return left;
        }

--------------------

## my\_lower\_bound代码实现 ##

--------------------

int my_lower_bound(vector<int>& nums,int target)
        { 
            int left = 0,right = nums.size();
            while(left < right)
            { 
                int mid = (left + right)/2;
                // 如果是小于的话 即left指针移动位置
                // 逼近大于等于的那个数 直到两个指针碰到一起
                if(nums[mid] < target) left = mid + 1;
                else right = mid; 
            }
            return left;
        }

--------------------

## 相关习题博客链接 自写upper\_bound lower\_bound函数 ##

--------------------

**下面的话 就贴一下在力扣中的相关习题链接就好了 大家可以去做一下 就当复习了 ^^**

**[剑指 Offer 53 - I. 在排序数组中查找数字 I（Easy）][Offer 53 - I. _ I_Easy]**  
**[Leetcode 剑指 Offer 53 - I. 在排序数组中查找数字 I（DAY 176）][Leetcode _ Offer 53 - I. _ I_DAY 176]**

[Offer 53 - I. _ I_Easy]: https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
[Leetcode _ Offer 53 - I. _ I_DAY 176]: https://love6.blog.csdn.net/article/details/120505725