Back to solutions

Find Minimum in Rotated Sorted Array

MediumBinary Search

A sorted array of distinct values was rotated at an unknown pivot. Find the minimum element in O(log n) time.

Open problem
Constraints
  • 1 <= nums.length <= 5000
  • All values are distinct
  • The array is a rotation of an ascending sorted array

Binary search on the pivot

Time O(log n)Space O(1)

Compare the middle element with the rightmost. If nums[mid] > nums[right], the minimum is to the right of mid; otherwise it is at mid or to its left. Narrow the range until it collapses onto the minimum.

#include <bits/stdc++.h>
using namespace std;

int findMin(vector<int>& nums) {
    int lo = 0, hi = nums.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi]) lo = mid + 1;
        else hi = mid;
    }
    return nums[lo];
}