[LeetCode] Search in Rotated Sorted Array

Link : Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array





Analysis:
First thought will be traverse and find rotation point.

Binary Search might be used here, but there is a big difference -- target array is rotated. So is binary search useless here? Think twice, and we find that if the boundary condition is carefully handled, binary search is still working here.

The middle cut might be in the first section, or the second section, depending on A[low] and A[mid]. And section selection is based on whether target is located in A[low]~A[mid] or A[mid]~A[high]. Other details is almost the same as in ordinary binary search. Code says!

 class Solution {  
 public:  
   int search(int A[], int n, int target) {  
     if(n<=0)  
       return -1;  
     int low=0, mid, high=n-1;  
     while(low<=high)  
     {  
       mid = (low+high)/2;  
       if(A[mid]==target) return mid;  
       if(A[mid]>=A[low])  
       {  
         if(A[low]<=target && target<=A[mid])  
           high = mid; // be careful about the index change, determine +1/-1 is needed or not  
         else  
           low = mid+1; // be careful about the index change, determine +1/-1 is needed or not  
       }  
       else  
       {  
         if(A[mid]<=target && target<=A[high])  
           low = mid; // be careful about the index change, determine +1/-1 is needed or not  
         else  
           high = mid-1; // be careful about the index change, determine +1/-1 is needed or not  
       }  
     }  
     return -1;  
   }  
 };