Finding Rotation Point
You'll learn: How to locate the pivot index where a sorted array was rotated using binary search in O(log n) time.
The Problem
Imagine a sorted array [1, 2, 3, 4, 5, 6, 7] that gets "rotated" at some unknown point. For example, rotating at index 3 gives [4, 5, 6, 7, 1, 2, 3]. Your job is to find where the rotation happened—the smallest element's index, which is the rotation point.
Why Binary Search Works
Even though the array isn't fully sorted anymore, it has a special property: it consists of two sorted segments. The rotation point is where the first segment ends and the second begins. This structure lets us use binary search!
The Core Idea
Compare the middle element with the rightmost element:
- If
mid > right, the rotation point is in the right half (the mid is part of the higher segment) - If
mid < right, the rotation point is in the left half or at mid itself (mid is part of the lower segment) - The smallest element (rotation point) is always where the sorted property "breaks"
Example Walkthrough
Array: [4, 5, 6, 7, 1, 2, 3]
- Check mid (7) vs right (3): 7 > 3, search right half
- Now in
[1, 2, 3], mid (2) vs right (3): 2 < 3, search left half - Found rotation point at index 4 (value 1)
Each step cuts the search space in half—that's your O(log n) efficiency!
Key Takeaway: The rotation point in a rotated sorted array can be found in O(log n) time by using binary search to detect where the sorted property breaks between two segments.