题目链接：剑指 Offer 53 - I. 在排序数组中查找数字 I

题目

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

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

示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

解题

一上来的方法

显然一个循环可以解决问题，时间复杂度$$O(n)$$

class Solution {
    public int search(int[] nums, int target) {
        int sum = 0;
        for(int i=0; i < nums.length; i++) {
            if (nums[i] == target)
                ++sum;
        }
        
        return sum;
    }
}

提交这个代码之后对性能并不满意，于是想改进一下。

改进（二分法）

注意到题目中提到了排序数组，数组是有序的，于是我便想到了折半查找，$$O(log n)$$的复杂度，好令人心动，说干就干，大体思路是：
先折半查找target值，如果找到，循环遍历查找的值的左边和右边（以第一个查找到的target为中心的邻域），统计目标值个数，找不到直接返回0。
正如折半查找的作者所说：“二分查找思想很简单，但细节是魔鬼。”，代码我反反复复改了好几次小细节，才最终通过。

一开始忘记了return结束循环超时，后面几次又因为左右边界问题导致越界、漏算，最终，终于成功通过。

具体实现

class Solution {
    public int search(int[] nums, int target) {
        if (nums.length == 1)
            return nums[0] == target ? 1 : 0;
        else if (nums.length == 0)
            return 0;

        int low = 0, high = nums.length - 1;
        int sum = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                int t = mid - 1;
                while (mid <= high && nums[mid] == target) {
                    ++sum;
                    ++mid;
                }
                while (t >= low && nums[t] == target) {
                    ++sum;
                    --t;
                }
                return sum;
            } else if (nums[mid] > target)
                high = mid - 1;
            else {
                low = mid + 1;
            }
        }

        return sum;
    }
}