剑指 Offer 53 - I. 在排序数组中查找数字 I

题目描述

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

输入输出

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

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

基本思路

二分法解决：转换为找到左边界left和右边界right后 right-left-1

在输入输出代码中即为 left = 2 right = 5

  1. 初始化： 左边界 i = 0 ，右边界 j = len(nums) - 1
  2. 循环二分： 当闭区间 i, j 无元素时跳出；
    1. 计算中点 m = (i + j) / 2（向下取整）；
    2. 若 nums[m] < target，则 target 在闭区间 [m + 1, j] 中，因此执行 i = m + 1；
    3. 若 nums[m] > target，则 target 在闭区间 [i, m - 1] 中，因此执行 j = m - 1；
    4. 若 nums[m] = target ，则右边界 right 在闭区间 [m+1, j] 中；左边界 left 在闭区间 [i, m-1] 中。因此分为以下两种情况：
      1. 若查找 右边界 right ，则执行 i = m + 1 ；（跳出时 i 指向右边界）
      2. 若查找 左边界 left ，则执行 j = m - 1 ；（跳出时 jj 指向左边界）
  3. 返回值： 应用两次二分，分别查找 right 和 left ，最终返回 right−left−1 即可。

java实现

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
37
38
39
40
41
class Solution {
    public int search(int[] nums, int target) {
        // 搜索右边界 right
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] <= target) i = m + 1;
            else j = m - 1;
        }
        int right = i;
        // 若数组中无 target ，则提前返回
        if(j >= 0 && nums[j] != target) return 0;
        // 搜索左边界 right
        i = 0; j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] < target) i = m + 1;
            else j = m - 1;
        }
        int left = j;
        return right - left - 1;
    }
}

// 包装成函数
// nums = [5,7,7,8,8,10]
// helper(nums, target)=5 helper(nums, target-1)=3
class Solution {
    public int search(int[] nums, int target) {
        return helper(nums, target) - helper(nums, target - 1);
    }
    int helper(int[] nums, int tar) {
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] <= tar) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
}