33. Search in Rotated Sorted Array

The key here is to check is the interval [lo, hi] is rotated or not. If it is rotated, there are two cases:

Case 1: nums[lo] > nums[mid]
In this case, the right part of nums[mid] must be sorted. If the target is in sorted part, we make the search interval to be the sorted part. Otherwise, we make the search interval to be the rotated part.

Case 2: nums[mid] > nums[hi]
In this case, the left part of nums[mid] must be sorted. Then do as Case 1.

By dealing with case 1 and case 2 above, we'll eventually make the target into a sorted search interval. And in this interval, we just search as normal binary search.

1:  class Solution {  
2:  public:  
3:    int search(vector<int>& nums, int target) {  
4:      int lo = 0, hi = nums.size()-1;  
5:      while (lo <= hi) {  
6:        int mid = lo + (hi - lo) / 2;  
7:        if (nums[mid] == target) return mid;  
8:        if (nums[lo] > nums[mid]) {  
9:          // there is rotation, the right part of mid is sorted  
10:          if (target > nums[mid] && target <= nums[hi]) lo = mid + 1;  
11:          else hi = mid - 1;  
12:        } else if (nums[hi] < nums[mid]) {  
13:          // there is rotation, the left part of mid is sorted  
14:          if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;  
15:          else lo = mid + 1;  
16:        } else {  
17:          // there is no rotation  
18:          if (target > nums[mid]) lo = mid + 1;  
19:          else hi = mid - 1;  
20:        }  
21:      }  
22:      return -1;  
23:    }  
24:  };