Find pivot (minimum) in a rotated sorted array

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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
}