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

题目：

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

思路：

其实一开始我想到的就是很简单，直接用空间换时间，直接哈希表解决，但看了书上的其实有更好的方法。

要观察数组的特性，这个数组有一个明显的特性就是有序性。对于要在数组中查找的到什么信息，只有在时间方面查找没办法提升效率我们才通常使用时间换空间的方法，但这里明显不需要空间换时间，在有序的数组中我们可以直接用二分查找的方法，直接降低时间复杂度。

如果我们按照平时的二分查找的方法，先找到中间值，然后分别向左向右找到第一个和最后一个来计算有多少个这个数字，n个数就可以出现o（n）次，顺序查找的时间复杂度就是o（n），显然时间复杂度过高。

观察上面的二分查找我们其主要的时间使用就是使用在查找第一个数，和最后一个。我们可以查找中间值后与k进行比较，如果中间值大于k证明k在中间值前面，如果小于就在中间值右边。如果中间值刚好是k，我们就可以看前一个数字是不是k，是的话就在前半段查找第一个k。同理找到最后一个k。用递归的思想就可以直接写出代码的实现；

代码实现：
 

int binarySearch(int* nums, int numsSize, int target, bool lower) {
    int left = 0, right = numsSize - 1, ans = numsSize;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] > target || (lower && nums[mid] >= target)) {
            right = mid - 1;
            ans = mid;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}
 
int search(int* nums, int numsSize, int target) {
    int leftIdx = binarySearch(nums, numsSize, target, true);
    int rightIdx = binarySearch(nums, numsSize, target, false) - 1;
    int ret = 0;
    if (leftIdx <= rightIdx && rightIdx < numsSize && nums[leftIdx] == target && nums[rightIdx] == target) {
        ret = rightIdx - leftIdx + 1;
    }
    return ret;
}