LeetCode 34. Find First and Last Position of Element in Sorted Array
原题链接
中等
作者:
tt2767
,
2022-04-01 22:24:18
,
所有人可见
,
阅读 150
/**
1. 有限顺序数列找值, 通过两次二分找到边界值
2. 找左边界:
将数组划分为[l, mid] 和 [mid+1, r], check 函数为 nums[mid] >= target, 这样r就会一直缩小到第一一个target 为止, start = r (找到后l == r)
3. 找右边界:
将数组划分为[l, mid-1] 和 [mid+1, r], check 函数为 nums[mid] > target, 这样l就会一直缩小到最后一个target 为止, start = l (找到后l == r)
*/
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] notFound = {-1, -1};
if (nums == null || nums.length ==0) return notFound;
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
if (nums[l] != target) return notFound;
int start = r;
l = 0;
r = nums.length-1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (nums[mid] > target) r = mid-1;
else l = mid;
}
int end = l;
return new int[]{start, end};
}
}