在排序数组中查找数字Ⅰ
统计一个数字在排序数组中出现的次数。
示例 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;
}
}