在排序数组中查找数字Ⅰ

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

示例 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;
    }
}