81. Search in Rotated Sorted Array II

Same idea of "33. Search in Rotated Sorted Array" but with one more case since there are duplicates.

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.

Case 3: nums[lo] == num[hi]
After excluding case 1 and case 2, there remaining condition is:
nums[lo] <= nums[mid] && nums[mid] <= nums[hi]
Since there are duplicates, all we need to deal with is the special case where nums[lo] == nums[hi]. And in this case, we only need to move lo and hi one step toward each other.

1:  class Solution {  
2:  public:  
3:    bool 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 true;  
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 if (nums[lo] < nums[hi]) {  
17:          // there is no rotation  
18:          if (target > nums[mid]) lo = mid + 1;  
19:          else hi = mid - 1;  
20:        } else {  
21:          lo++;  
22:          hi--;  
23:        }  
24:      }  
25:      return false;  
26:    }  
27:  };