AI Hints
Home›DSA in Python Tutorial›More Practice: Heaps, Search and DP
DSA in Python · Lesson 119 of 132

Practice: Search a Rotated Array

Binary search with a twist.

⏱ 2 min read▶ Video at 2:21:57🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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?

Practice: Search a Rotated Array
From the video: Practice: Search a Rotated Array
  • 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.

rotated.pypython
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))
Output
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.

keyvalue
Key factone half is sorted
Checkis the target in it?
Discardthe other half
CostO(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)
Next up: Practice: Longest Increasing Subsequence — DP over endings