剑指 Offer 53 - I. 在排序数组中查找数字 I（LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置）——二分

题目链接：

• https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
• https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

题目： 

统计一个数字在排序数组中出现的次数。 

解法：

 两次二分，分别找左右边界，时间O(logN)，空间O(1)

本题二分关键是，弄清二分结束后左右下标的位置。

左边界：如下代码用于寻找左边界

while(l<=r) {
    int mid = (l+r)>>1;
    if(nums[mid] >= target) {
        r = mid - 1;
    } else {
        l = mid + 1;
    }
}

 上述循环结束后，左右指针指向如下图所示

 

 右边界：如下代码用于寻找右边界

while(l<=r) {
    int mid = (l+r)>>1;
    if(nums[mid] <= target) {
        l = mid + 1;
    } else {
        r = mid - 1;
    }
}

上述循环结束后，左右指针指向如下图所示

代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        while(l<=r) {
            int mid = (l+r)>>1;
            if(nums[mid] >= target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        int lower_bound = l;
        // cout << "l = " << l;
        l = 0, r = nums.size() - 1;
        while(l<=r) {
            int mid = (l+r)>>1;
            if(nums[mid] <= target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        int upper_bound = r;
        // cout << ", r = " << r << endl;
        return upper_bound - lower_bound + 1;
    }
};

int main()
{
    Solution slu;
    vector<int> v1 = {5,7,7,8,8,10};
    vector<int> v2 = {5,7,7,8,8,10};
    vector<int> v3 = {1};
    int t1 = 8, t2 = 6, t3 = 1;
    cout << slu.search(v1, t1) << endl;
    cout << slu.search(v2, t2) << endl;
    cout << slu.search(v3, t3) << endl;
    return 0;
}