Monday, August 4, 2014

[LeetCode] Search for a range


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].


解题思路:
利用二分搜索法分别找到beginindex 和 endindex.

Java Code:

  public int[] searchRange(int[] A, int target) {
        int[] result = new int[2];
        
        result[0] = searchRange1(A, target, true);
        result[1] = searchRange1(A, target, false);
        
        return result;
    }
    
    //binary search for beginIndex and endIndex respectily 
     public int searchRange1(int[] A, int target, boolean first){
           int start = 0, end = A.length - 1;
           int index = -1;
           
           while(start <= end){
               int middle = (start + end)/2;
               
               if(A[middle] > target){
                   end = middle - 1;
               }
               
               if(A[middle] < target){
                   start = middle + 1;
               }
               
               if(A[middle] == target){
                   index = middle;
                   
                   if(first) end = middle-1;
                   else start = middle + 1;
               }
           }
          
           return index;
    }

No comments:

Post a Comment