題目
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
答案
class Solution {
public int[] searchRange(int[] nums, int target) {
int l = 0, r = nums.length, candidate = -1;
while(l < r) {
int mid = (l + r) / 2;
if(nums[mid] < target) {
l = mid + 1;
}
else if(nums[mid] > target) {
r = mid;
}
else {
// found
candidate = mid;
break;
}
}
if(candidate == -1) return new int[]{-1,-1};
r = l = candidate;
while(l >= 0 && nums[l] == target) l--;
while(r < nums.length && nums[r] == target) r++;
return new int[] {l+1, r-1};
}
}
