Code Logo

Find Minimum in Rotated Sorted Array

Published at24 Jul 2026
Created by
Medium 0 views
Like0

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example,

[3,4,5,1,2]

is a rotation of

[1,2,3,4,5]

. Given a rotated unique-valued array, find the minimum element in O(log n) time.

The minimum element is the only element smaller than its left neighbor — this is the pivot point where the rotation occurred. Binary search narrows down to this pivot by comparing the middle element with the rightmost element. If the middle is greater than the rightmost, the minimum must be in the right half (the unsorted part). Otherwise, the minimum is in the left half (including the middle).

Unlike searching for a target value, this binary search variant does not compare against a fixed target. Instead it compares the middle element with the right boundary to determine which side contains the rotation point. The algorithm converges to the smallest element as the search range shrinks.

Edge cases include a single-element array (return that element), an array rotated n times (back to original order — minimum is first element), and an array with two elements. The array has no duplicates (LeetCode version).

This variant of binary search uses the right boundary rather than a fixed target value. By comparing nums[mid] with nums[hi], we determine which side contains the rotation point. When nums[mid] > nums[hi], the right half has the rotation, so we move lo to mid+1. Otherwise, hi becomes mid. This simple rule guarantees convergence to the minimum.

Example Input & Output

Example 1
Input
[1]
Output
1
Explanation

Single element.

Example 2
Input
[4,5,6,7,0,1,2]
Output
0
Explanation

Minimum 0 at index 4.

Example 3
Input
[11,13,15,17]
Output
11
Explanation

No rotation, minimum is first element.

Example 4
Input
[3,4,5,1,2]
Output
1
Explanation

Minimum 1 is at the pivot.

Example 5
Input
[2,1]
Output
1
Explanation

Two elements, rotated once.

Algorithm Flow

Recommendation Algorithm Flow for Find Minimum in Rotated Sorted Array
Recommendation Algorithm Flow for Find Minimum in Rotated Sorted Array

Solution Approach

Binary search with right comparison: if nums[mid] > nums[hi], min is on the right; else min is on the left (or mid).

<p>function solution(nums) {
  var lo = 0, hi = nums.length - 1;
  while (lo</p>< hi) {
    var mid = Math.floor((lo + hi) / 2);
    if (nums[mid] ><p>nums[hi]) lo = mid + 1;
    else hi = mid;
  }
  return nums[lo];
}</p>

Time O(log n), Space O(1).

Best Answers

java
class Solution {
    public int solution(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] > nums[hi]) lo = mid + 1;
            else hi = mid;
        }
        return nums[lo];
    }
}