面试题53 - Ⅰ. 在排序数组中查找数字Ⅰ

面试题53 - Ⅰ. 在排序数组中查找数字Ⅰ

Scroll Down

在排序数组中查找数字Ⅰ

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

示例 1:

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

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

思路

二分法,确定左右边界。

  • 计算中点 m = (i + j) / 2;
  • 若 nums[m] < target,则 target 在闭区间 [m + 1, j] 中,因此执行 i = m + 1;
  • 若 nums[m] > target,则 target 在闭区间 [i, m - 1] 中,因此执行 j = m - 1;
  • 若 nums[m] = target,则右边界 right在闭区间 [m+1, j] 中;左边界 left 在闭区间 [i, m-1] 中。因此分为以下两种情况:
    • 若查找 右边界 right,则执行 i = m + 1;(跳出时 i 指向右边界)
    • 若查找 左边界 left,则执行 j = m - 1;(跳出时 j 指向左边界)

解答

class Solution {
    public int search(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        int right = 0, left = 0;
        
        while (i <= j) {
            int mid = (j - i) / 2 + i;
            if (nums[mid] <= target) i = mid + 1;
            else j = mid - 1;
        }
        right = i;

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

        return right - left - 1;
    }
}