Given a sorted array of integers, 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]
.
For example,
Given
return
Solution 1: use 2 binary search. Search left and right to combine the result. Do not forget the initial judgement. if target<nums[0] or >nums[n-1] do not need search.Given
[5, 7, 7, 8, 8, 10]
and target value 8,return
[3, 4]
. public class Solution {
public int[] searchRange(int[] nums, int target) {
int lo=0, hi=nums.length-1;
if (target<nums[lo] || target>nums[hi]) return new int[]{-1,-1};
while (lo<hi) {
int mid=lo+(hi-lo)/2;
if (nums[mid]>=target) hi=mid;
else lo=mid+1;
}
int left=lo;
lo=0;
hi=nums.length-1;
while (lo<hi) {
int mid=hi-(hi-lo)/2;
if (nums[mid]<=target) lo=mid;
else hi=mid-1;
}
int right=lo;
if (left>right) return new int[]{-1,-1};
return new int[]{left,right};
}
}
没有评论:
发表评论