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

[剑指 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
1
2
3
4
5
6
7
8
9

题解

排序数组查找，首先想到二分法

• 寻找一个数字在数组中出现的次数，可以理解为找这个数的左右边界
• 这个数字的个数就等于：right − left − 1
• 步骤：
• 第一步：查找目标对象右边界
  • nums[mid] <= target，继续在 【mid+1,j】寻找，否则在【i,mid-1】
• 第二步：判断是否找到目标对象
• 第三步：查找目标对象左边界
  • nums[mid] < target，继续在 【mid+1,j】寻找，否则在【i,mid-1】
• 第四步：返回结果（右边界 - 左边界 - 1）

class Solution {
    public int search(int[] nums, int target) {

        //右边界
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int mid = (i + j) / 2;
            if(nums[mid] <= target) i = mid + 1;
            else j = mid - 1;
        }
        int right = i;

        // 确认是否存在
        if(j >= 0 && nums[j] != target) return 0;

        //左边界
        i = 0; j = nums.length - 1;
        while(i <= j) {
            int mid = (i + j) / 2;
            if(nums[mid] < target) i = mid + 1;
            else j = mid - 1;
        }
        int left = j;

        return right - left - 1;
    }
}
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

---