# Share my recursive and iterative Python solution with detailed explanation, O(n) worst case

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

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

2. 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):
# does not exist
return False
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, middle-1, target) or searchHelper(nums, middle, tail-1, 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, 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
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