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

题目链接

题意

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

示例

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

题解

这题很容易被题目标题和内容搞晕。题目内容是查找树，题意是统计数的次数。如果关注题意的话，就会自然被引导去想用hash或者什么数组结构去统计。但这却不是最优解。
应该从标题出发，理解题目为

在排序数组中查找一个数字，并返回该数字出现的次数。

那么我们就会联想到用二分查找去做。通过二分查找，找到该数在数组中的左右边界，进行运算就能得到其出现次数了。

代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        int mid, left, right;
        //搜索target的右边界
        while (l <= r) {
            mid = (l + r) / 2;
            if (nums[mid] <= target) l = mid + 1;
            else r = mid - 1;
        }
        right = l;
        //搜索右边界的目的是找target右边的那一个位置，所以当搜索结束，而右边界的左边不是target的话，就说明target不存在。
        if (r >= 0 && nums[r] != target) return 0;
        //搜素左边界，这里r已经是表示右边界的左边一位了，所以直接以这个位置作为左边界搜索的末端即可。
        l = 0;
        while (l <= r) {
            mid = (l + r) / 2;
            if (nums[mid] >= target) r = mid - 1;
            else l = mid + 1;
        }
        left = r;
        return right - left - 1;
    }
};