lower_bound和upper_bound的C++实现

lower_bound

class Solution {
public:
    int my_lower_bound(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l <= r)
        {
            int mid = l + ((r - l) >> 1);   //防止溢出
            if(target <= nums[mid])         //注意此处与传统二分不同
                r = mid - 1;
            else
                l = mid + 1;
        }
        return l;
    }
};

upper_bound

class Solution {
public:
    int my_upper_bound(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l <= r)
        {
            int mid = l + ((r - l) >> 1);   //防止溢出
            if(target >= nums[mid])         //注意此处与传统二分不同
                l = mid + 1;
            else
                r = r - 1;
        }
        return l;
    }
};