1
class Solution {
2
  public boolean search(int[] nums, int target) {
3
    if (nums == null || nums.length == 0) return false;
4

5
    int left = 0, right = nums.length - 1;
6
    int start = 0;
7

8
    // 1. find index of the smallest element
9
    while (left < right) {
10
      while (left < right && nums[left] == nums[left + 1]) ++left;
11
      while (left < right && nums[right] == nums[right - 1]) --right;
12
      int mid = left + (right - left) / 2;
13
      if (nums[mid] > nums[right]) {
14
        left = mid + 1;
15
      } else right = mid;
16
    }
17

18
    // 2. figure out in which side our target lies
19
    start = left;
20
    left = 0;
21
    right = nums.length - 1;
22
    if (target >= nums[start] && target <= nums[right]) left = start;
23
    else right = start;
24

25
    // 3. Run normal binary search in sorted half.
26
    while (left <= right) {
27
      int mid = left + (right - left) / 2;
28
      if (nums[mid] == target) return true;
29

30
      if (nums[mid] > target) right = mid - 1;
31
      else left = mid + 1;
32
    }
33

34
    return false;
35
  }
36
}