剑指 Offer 53 - I. 在排序数组中查找数字 I

剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣（LeetCode）

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

思路：

---

二分分别查找两个端点再计算

复杂度：

​ O(n)

题解：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        /* 搜索右边界 right */
        int i = 0, j = nums.size() - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] <= target) i = m + 1;
            else j = m - 1;
        }
        int right = i;
        /* 若数组中无 target ，则提前返回 */
        if(j >= 0 && nums[j] != target) return 0;
        /* 搜索左边界 right */
        i = 0; j = nums.size() - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] < target) i = m + 1;
            else j = m - 1;
        }
        int left = j;
        return right - left - 1;
        
    }
};