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

Finding Rotation Point

Use binary search to identify the pivot index where a sorted array was rotated in O(log n) time.

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]

  1. Check mid (7) vs right (3): 7 > 3, search right half
  2. Now in [1, 2, 3], mid (2) vs right (3): 2 < 3, search left half
  3. 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.