53 - I. 在排序数组中查找数字 I.md

解题思路

1. 直接找

遍历过程中统计次数

func search(nums []int, target int) int {
    count := 0
    for _, v := range nums {
        if v == target {
            count++
        }
    }
    return count
}

2. 二分搜索

由于原数组是有序的，可以使用二分搜索

二分搜索中，当等于 target，找最左边界，这样返回的是 target 最左起始位 l 当等于 target+1 时，返回的是 target+1 的最左起始位 r，r-l 正好是 target 的个数

func search(nums []int, target int) int {
    l := binarySearch(nums, target)
    r := binarySearch(nums, target+1)
    return r-l
}

func binarySearch(nums []int, target int) int {
    l, r := 0, len(nums)-1
    for l <= r {
        mid := l + (r-l) >> 1
        if nums[mid] >= target {
            r = mid-1
        } else {
            l = mid+1
        }
    }
    return l
}