Wednesday, December 10, 2014

Search in Rotated Sorted Array LeetCode II

Only One situation need to be done.
When A[L] == A[mid].

public boolean search(int[] A, int target) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
         int L = 0;
       int R = A.length-1;
   
       while (L<=R) {
           int mid = (L+R)/2;
           if (A[mid] == target) return true;
       
           // Example: 4 5 6 7 8 9 1 2 3
           if (A[L] < A[mid]) {
               if (A[L]<=target && target < A[mid]) {
                   R = mid - 1;
               } else {
                   L = mid + 1;
               }
           }
           // Example: 8 9 1 2 3 4 5 6 7
           else if (A[L] > A[mid]) {
               if (A[mid] < target && target <= A[R]) {
                   L = mid + 1;
               } else {
                   R = mid - 1;
               }
           } else {
               L++;
           }
       }
       return false;
    }

No comments:

Post a Comment