Find the Rotation Point

Difficulty: Easy · Pattern: Binary Search · Concept: General Coding (DSA) — Core Patterns to Drill

A sorted array of distinct integers has been rotated some unknown number of times (e.g. [1,2,3,4,5] rotated twice becomes [4,5,1,2,3]). Find the index of the minimum element — the "rotation point" where the sequence wraps around. If the array wasn't rotated at all, that's index 0.

Even though the array isn't globally sorted anymore, it's still sorted in two contiguous halves — which is the signal that binary search still applies, just with a different comparison than the textbook version.

Your task: implement find_rotation_point(arr) in $O(\log n)$ time — a linear scan defeats the point.

Implement it yourself

assert find_rotation_point([4, 5, 6, 7, 0, 1, 2]) == 4
assert find_rotation_point([1, 2, 3, 4, 5]) == 0
assert find_rotation_point([3, 4, 5, 1, 2]) == 3
assert find_rotation_point([2, 1]) == 1
assert find_rotation_point([5, 1, 2, 3, 4]) == 1

Next: Search in a Rotated Sorted Array (a harder variant), or continue to Maximum Non-Adjacent Sum