```
public bool Search(int[] nums, int target) {
int sIndex = 0, left = 0, right = nums.Length - 1;
//1. find the smallest element O(lgN) with worst O(N)
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] > nums[right]) left = mid + 1;
else if (nums[mid] < nums[right]) right = mid;
else
while (right > mid && nums[right] == nums[mid]) right--;
if (right != mid) {
if (nums[right] > nums[mid]) left = ++right;
else left = right;
}
}
sIndex = nums[right] > nums[0] ? 0 : right;
//2. Identify the value range
if (sIndex != 0 && target >= nums[0]) { left = 0; right = sIndex - 1; }
else { left = sIndex; right = nums.Length - 1; }
//3. Binary search it O(lgN)
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) return true;
else if (nums[mid] > target) right = mid - 1;
else left = mid + 1;
}
return false;
}
```