Saturday, January 3, 2015

Search for a Range (LeetCode Array)

Question: 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 [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