33. Search in Rotated Sorted Array Leetcode Java

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.

Solution:

All related problems:

33. Search in Rotated Sorted Array

81. Search in Rotated Sorted Array II 

153. Find Minimum in Rotated Sorted Array

154. Find Minimum in Rotated Sorted Array II

Modified binary search

If we compare the middle element with the right element, we can determine which part of the array is sorted. 

Eg. the example in the question 4,5,6,7,0,1,2. Middle element is 7 and is greater than the right element so the left part of the array is sorted, then we can check if the target is in the left part, if yes, update the right pointer, if no, update the left pointer. Vice versa. 

Time complexity: O(logn) each time we will cut the array half

 public int search(int[] A, int target) {  
     if(A==null || A.length==0) return -1;  
     int l=0;  
     int r=A.length-1;  
     while(l<=r){  
       int m=(r-l)/2+l;  
       if(A[m]==target) return m;  
       if(A[m]<A[r]){ // right part is sorted  
         if(target>A[m] && target<=A[r]) l=m+1;  
         else r=m-1;  
       }  
       else{ // left part is sorted  
        if(target<A[m] && target>=A[l]) r=m-1;  
        else l=m+1;  
       }  
     }  
     return -1;  
   }