[9.3] Find an element ain rotated sorted array

1. Example

Make sure only SORTED side can use Binary Search

For example, if the array is [2,2,2,2,2,2,2,2,3,2,2,2,2,2,2,2,2,2,2], there is no way to find element 3 until you do a linear search.

s= {15,16,19,20,1,3,4,5,7,10,14}
Find 5 in array s
Output : 8 (the index of 5 in the array)


2. Implementation

public static int search(int[] a, int l, int r, int target)
{





     if ( a == null || a.length == 0)
        return -1;






     while ( l <= r )
     {






         int m = (l+r) /2 ;
         if (  a[m] == x )
              return m;






         if ( a[l] < a[m]  )
         {





               //if (a[m]  >  x)
               // NOTE: consider another side with "="
               if ( a >= a[l] && a < a[m] )
                     r = m-1;






               else 
                     l = m+1;
               
         }
         else if ( a[l] > a[m] )
         {






               // NOTE: consider another side with "="
               if ( x > a[m] && x <= a[r] )
                   l= m+1;





               else
                   r = m-1;
               //if ( a[m] > x )
               //     r = m-1;
               //else 
               //     l = m+1;     
               
         }  
         else 
         {
              l = l +1;
         }





     }



     return -1;



}

3. Similar Ones