一、题目描述

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

示例 1:

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

示例 2:

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

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

二、我的题解 – 非全部遍历

由于数组是非递减的，那么 target 数如果有多个，也一定是相连的。

所以我的方法是：

找到第一个 target
往后遍历计数，直到不等于 target

代码：

func search(nums []int, target int) int {

    if len(nums) == 0{
        return 0
    }
    
    i:=0
    for nums[i]!=target {
        i++
        if i == len(nums){
            return 0
        }
    }
    
    s := 0
    for nums[i] == target {
        s++
        i++
        if i == len(nums) {
            return s
        }
    }
    
    return s

}

评判结果：

三、二分法

其实一拿到题目，看到递增数组，我的第一反应就是二分法，但是感觉这个写出来没上面的简洁，也没上面的容易理解。

思路：

i,j:= 0,len(nums)-1，两个指针表示一个区间，通过比较区间中值和 target 的大小关系，不断缩小区间。
直到区间中值指到 target ，跳出。
令 i,j 分别等于当前中值 m,m+1，i 向前找有多少个 target ，j 向后找有多少个 target 。加起来就是 target 总数。

代码：

func search(nums []int, target int) int {
    if len(nums) == 0{
        return 0
    }else if len(nums) == 1 && nums[0] == target{
        return 1
    }
    
    i,j,m := 0,len(nums)-1,0

    for i < j {
        m = i+(j-i)/2
        if nums[m]<target{
            i = m+1
        }else if nums[m]>target{
            j = m-1
        }else{
            break
        }
    }

    s:= 0

    if i == j && nums[i]==target{
        return 1
    }
    if i!=j{
        i,j = m,m+1
        for nums[i]==target{
            s++
            i--
            if i == -1{
                break
            }
        }
        for nums[j]==target{
            s++
            j++
            if j == len(nums){
                break
            }
        }
    }
    
     return s
   
}