Find pivot (minimum) in a rotated sorted array
Problem
A sorted array of distinct values was rotated at an unknown point. Return its minimum element (the rotation point) in O(log n) time.
Example 1
Input: [3, 4, 5, 1, 2] Output: 1
Example 2
Input: [11, 13, 15, 17] Output: 11
Not rotated.
Also asked as: Find pivot element in a sorted array
Test cases
Case 1
Input: [3,4,5,1,2] Expected: 1
Case 2
Input: [4,5,6,7,0,1,2] Expected: 0
Case 3
Input: [11,13,15,17] Expected: 11
View solutionHide solution1 approach
1. Binary search for the rotation point
Time O(log n)Space O(1)
If a[mid] > a[hi] the minimum is to the right of mid; otherwise it is mid or to the left.
function findMin(a) { let lo = 0, hi = a.length - 1; while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] > a[hi]) lo = mid + 1; else hi = mid; } return a[lo]; // lo is the rotation (pivot) index}