The idea is simple. Use binary search. Let H, M and T be the number at head, middle and tail, respectively.

H == M == T: target could be in either half, we need to search both half

otherwise we can continue binary search, just find the right half. If the order pattern is any of the following ones, the target must be in the upper half if it exists, otherwise lower half
a. H <= M < Target : H to M is sorted and target is bigger than M (biggest in lower half)
b. Target < H <= M; H to M is sorted and target is smaller than H (smallest in lower half)
c. T >= Target > M: M to T is sorted and target is within range
Recursive one
class Solution:
# @param {integer[]} nums
# @param {integer} target
# @return {boolean}
def search(self, nums, target):
def searchHelper(nums, head, tail, target):
if head > tail:
# does not exist
return False
middle = (head + tail)//2
if nums[middle] == target:
return True
if nums[head] == nums[tail] == nums[middle]:
# worst case, target could be in either half
return (searchHelper(nums, head, middle1, target) or searchHelper(nums, middle, tail1, target))
if (nums[head] <= nums[middle] < target) or (target < nums[head] <= nums[middle]) or (nums[tail] >= target > nums[middle]):
return searchHelper(nums, middle+1, tail, target)
return searchHelper(nums, head, middle1, target)
return searchHelper(nums, 0, len(nums)1, target)
Iterative one:
class Solution:
# @param {integer[]} nums
# @param {integer} target
# @return {boolean}
def search(self, nums, target):
head, tail = 0, len(nums)  1
while head <= tail:
middle = (head + tail)//2
if nums[middle] == target:
return True
if nums[head] == nums[tail] == nums[middle]:
# worst case, target could be in either half, move tail by one step
tail = 1
elif (nums[head] <= nums[middle] < target) or (target < nums[head] <= nums[middle]) or (nums[tail] >= target > nums[middle]):
# target must be in the upper half if it exists
head = middle + 1
else:
# target must be in the lower half if it exists
tail = middle  1
return False