Practice: Search a Rotated Array
Binary search with a twist.
A sorted list has been rotated, so it starts in the middle. Like four, five, six, seven, zero, one, two. Find the position of a target in O of log N. Plain binary search breaks. Pause. What's still true about each half?

- A sorted list, rotated
- 4, 5, 6, 7, 0, 1, 2
- Still O(log n)?
One half is always sorted
Cut the list in the middle, and at least one half is still properly sorted. We check which half is sorted, and whether the target lies inside it. If it does, search there. If not, search the other half. Run it. Zero is at position four, and three isn't there at all.
def search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]: hi = mid - 1
else: lo = mid + 1
else:
if nums[mid] < target <= nums[hi]: lo = mid + 1
else: hi = mid - 1
return -1
print(search([4, 5, 6, 7, 0, 1, 2], 0), search([4, 5, 6, 7, 0, 1, 2], 3))4 -1
The lesson
Binary search doesn't need a perfectly sorted list. It needs a rule that lets you throw away half the possibilities at every step. Whenever you can find a rule like that, the answer is O of log N. Interviewers love this twist.
| key | value |
|---|---|
| Key fact | one half is sorted |
| Check | is the target in it? |
| Discard | the other half |
| Cost | O(log n) |
Summary
In a rotated list, one half is always sorted, so we can still discard half each step. Next, a classic dynamic programming problem.
Key takeaways- Find the sorted half
- Is the target inside?
- O(log n)