Course contentsShow
← Computer Science
Lesson 816 of 2,87219. Searching and SelectionFree lesson

Binary Search on Rotated Sorted Arrays

Adapt binary search to work on arrays that have been rotated at an unknown pivot point.

Binary Search on Rotated Sorted Arrays

What you'll learn: How to adapt binary search to find elements in a sorted array that has been rotated at an unknown pivot point.

The Problem

Imagine a sorted array [1, 2, 3, 4, 5, 6, 7] that someone rotated by moving elements from the front to the back, creating [4, 5, 6, 7, 1, 2, 3]. The array is still sorted in two pieces, but the rotation breaks the standard binary search assumption. How can we still search in O(log n) time?

The Core Insight

The key is recognizing that in any rotated sorted array, at least one half of your search space is always properly sorted. When you pick a midpoint, either the left side or the right side will be in ascending order. Once you identify which half is sorted, you can determine whether your target belongs in that sorted half or the other half.

The Strategy

  1. Find the middle element
  2. Determine which half (left or right) is properly sorted by comparing the middle with the endpoints
  3. Check if your target falls within the range of the sorted half
  4. If yes, search that half; if no, search the other half
  5. Repeat until found or space exhausted

Think of it like searching for a book on two separate sorted shelves that were once one continuous shelf—you just need to figure out which shelf your book would logically be on.

Why This Works

Because rotation preserves the sorted property within segments, we can eliminate half the search space in each step by making logical comparisons, maintaining O(log n) time complexity.

Key Takeaway: Binary search works on rotated sorted arrays by identifying which half is properly sorted at each step, then deciding whether the target must be in that sorted half or the rotated half.