剑指 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

提示：

0 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
nums 是一个非递减数组
-10⁹ <= target <= 10⁹

解法一：二分搜索

使用二分搜索在 nums 数组中找到第一个大于等于 target 的元素的索引 i，第一个大于 target 的元素的索引 j，问题的答案即为 j - i。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


func getGreaterOrEqual(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] >= target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return left
}

func getGreater(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] > target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return left
}

func search(nums []int, target int) int {
    return getGreater(nums, target) - getGreaterOrEqual(nums, target)
}

另一种实现代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


// 大于等于指定元素的数字中的最小值
func greaterOrEqual(nums []int, target int) int {
    n := len(nums)
    left, right := 0, n
    for left < right {
        // mid != right 肯定为 true
        mid := left + (right-left)/2
        if nums[mid] >= target {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

// 大于指定元素的数字中的最小值
func greater(nums []int, target int) int {
    n := len(nums)
    left, right := 0, n
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > target {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func search(nums []int, target int) int {
    a := greaterOrEqual(nums, target)
    b := greater(nums, target)
    return b - a
}