Binary Search on Rotated and Unsorted Arrays
Solve search-in-rotated-sorted-array and find-minimum-in-rotated-array by deciding which half is sorted at each step.
What Is a Rotated Sorted Array?
A rotated sorted array is a sorted array that has been cut at some pivot and the two pieces swapped. For example, [4, 5, 6, 7, 0, 1, 2] is the sorted array [0,1,2,4,5,6,7] rotated at index 4. Standard binary search fails here because the array is no longer globally sorted.
The key insight is that at least one half of the array is always sorted after any rotation. Your binary search must identify which half is sorted before deciding where to move the boundaries.
# A rotated sorted array — one half is always sorted
arr = [4, 5, 6, 7, 0, 1, 2]
# Left half [4,5,6,7] is sorted
# Right half [0,1,2] is also sorted
# But left[0]=4 > right[-1]=2 => rotation happened in left-to-right crossingIdentifying the Sorted Half
After computing mid, compare arr[lo] with arr[mid]. If arr[lo] <= arr[mid], the left half is sorted; otherwise the right half is sorted. Once you know which half is sorted, you can check whether the target falls within that sorted range and narrow the search accordingly.
This decision tree lets you discard exactly half the array per step, preserving the O(log n) complexity even in a rotated array.
def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
# Left half is sorted
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
# Right half is sorted
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0)) # 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3)) # -1All lessons in this course
- Classic Binary Search: Left, Right, Mid
- Binary Search on Rotated and Unsorted Arrays
- Lower Bound and Upper Bound
- Answer-Space Binary Search