## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Search in rotated sorted array challenge

Sharing is caring!

Problem statement
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., $\left[0, 1, 2, 4, 5, 6, 7\right]$ might become $\left[4, 5, 6, 7, 0, 1, 2\right]$).

You are given a target value to search. If found in the array return its index, otherwise return $-1$.

You may assume no duplicate exists in the array.

Solution

class Solution(object):
def binarySearch(self, nums, n, start, end):
if start <= end:
mid = start + (end - start) // 2

if n == nums[mid]:
return mid
elif n < nums[mid] and n < nums[start]:
if nums[start] > nums[mid]:
# left
return self.binarySearch(nums, n, start, mid-1)
else:
# right
return self.binarySearch(nums, n, mid+1, end)
elif n < nums[mid]:
# left
return self.binarySearch(nums, n, start, mid-1)
elif n > nums[mid] and n > nums[end]:
if nums[start] < nums[mid]:
# right
return self.binarySearch(nums, n, mid+1, end)
else:
# left
return self.binarySearch(nums, n, start, mid-1)
elif n > nums[mid]:
# right
return self.binarySearch(nums, n, mid+1, end)

else:
return -1

def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
return self.binarySearch(nums, target, 0, len(nums)-1)

def main():
solution = Solution()
print(solution.search([4, 5, 6, 7, 0, 1, 2], 0)) # 4
print(solution.search([4, 5, 6, 7, 0, 1, 2], 1)) # 5
print(solution.search([4, 5, 6, 7, 0, 1, 2], 2)) # 6
print(solution.search([4, 5, 6, 7, 0, 1, 2], 4)) # 0
print(solution.search([4, 5, 6, 7, 0, 1, 2], 5)) # 1
print(solution.search([4, 5, 6, 7, 0, 1, 2], 6)) # 2
print(solution.search([4, 5, 6, 7, 0, 1, 2], 7)) # 3

print(solution.search([4, 5, 6, 7, 8, 1, 2, 3], 8)) # 4
print(solution.search([5, 1, 2, 3, 4], 1)) # 1

if __name__ == "__main__": main()