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 [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
Idea: We need to use two binary searches. The first binary search is to find the left boundary. The second binary search is to find the right boundary.
Time: O(lgn) Space: O(1)
Code:
public class Solution {
public int[] searchRange(int[] A, int target) {
int left=0;
int right=A.length-1;
int[] result={-1,-1};
while(left<right)
{
int mid=(left+right)/2;
if(A[mid]<target)
left=mid+1;
else
right=mid;
}
int leftBound=(A[left]==target)?left:-1;
if(leftBound==-1)
{
return result;
}
left=leftBound;
right=A.length;
while(left<right)
{
int mid=(left+right)/2;
if(A[mid]<=target)
left=mid+1;
else
right=mid;
}
result[0]=leftBound;
result[1]=left-1;
return result;
}
}
No comments:
Post a Comment