又见二分查找

Idea

The key to binary search is Don’t try to find the exact answer, but find a split point m such that for all n, n >= m, conditions are satisfied, the m will naturally become the answer for free.

Template

l = lowerest, r = highest
while l <= r :
    m = l + (r - l) / 2
    if cond(m) :
        r = m - 1
    else : 
        l = m + 1
return l

// Return the smallest x such that cond(x) is true, 
// if not found return the initial value of r.     

binary_search

int binary_search(vector<int>& nums, int target) {
    const int n = nums.size();
    int l = 0, r = n - 1;
    while(l <= r) {
        int m = l + (r - l) / 2;
        if(nums[m] == target) return m;
        else if(nums[m] > target) r = m - 1;
        else l = m + 1;
    }
    return l;
}

lower_bound

int my_lower_bound(vector<int>& nums, int target) {
    const int n = nums.size();
    int l = 0, r = n - 1;
    while(l <= r) {
        int m = l + (r - l) / 2;
        if(nums[m] >= target) r = m - 1;
        else l = m + 1;
    }
    return l;
}

upper_bound

int my_upper_bound(vector<int>& nums, int target) {
    const int n = nums.size();
    int l = 0, r = n - 1;
    while(l <= r) {
        int m = l + (r - l) / 2;
        if(nums[m] > target) r = m - 1;
        else l = m + 1;
    }
    return l;
}

使用

int main() {
    vector<int> nums{1,2,3,4,4,5,7};
    for(int& e : nums) {
        cout << binary_search(nums, e) << " "
             << my_lower_bound(nums, e) << " "
             << my_upper_bound(nums, e) << endl;
    }
    return 0;
}

// output
// 0 0 1
// 1 1 2
// 2 2 3
// 3 3 5
// 3 3 5
// 5 5 6
// 6 6 7

Reference：huahualeetcode