Leetcode 33 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.

Solution 1: Still binary search with more conditions. Especially careful with termination condtion.

 public class Solution {  
   public int search(int[] nums, int target) {  
     int lo=0, hi=nums.length-1;  
     while (lo<=hi) {  
       int mid=lo+(hi-lo)/2;  
       if (nums[mid]==target) return mid;  
       if (nums[lo]<=nums[hi]) { //not rotate any more, pay attention when lo=mid here  
         if (nums[mid]<target) lo=mid+1;  
         else hi=mid-1;  
       }  
       else { //still rotate  
         if (nums[mid]>=nums[lo]) { //pivot on the right of mid  
           if (target>nums[mid] || target<nums[lo]) lo=mid+1;  
           else hi=mid-1;  
         }  
         else { //pivote on the left of mid (include mid)  
           if (target<nums[mid] || target>nums[hi]) hi=mid-1;  
           else lo=mid+1;  
         }  
       }  
     }  
     return -1;  
   }  
 }