This problem follows the Modified Binary Search pattern, commonly found in the Binary Search category. Recognizing this pattern is key to solving it efficiently in an interview setting.
Determine which half is sorted. Check if target is in the sorted half.
At least one half is always sorted in a rotated array — determine which half is sorted, then check if the target is in that range.
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target: return mid
if nums[left] <= nums[mid]: # left half sorted
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else: # right half sorted
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1Practice Search in Rotated Sorted Array and similar Binary Search problems with flashcards. Build pattern recognition through active recall.
Practice this problem