Command Palette

Search for a command to run...

Hectal
Problem 11.5 · Binary SearchMedium

Find Minimum in Rotated Sorted Array

PatternBinary Search on an Index

What it teaches: Find the rotation point by comparing mid with the right end: the first-true template again.

Practise it on judges as “Find Minimum in Rotated Sorted Array”.

The problem

Return the minimum of a rotated sorted array of distinct values in O(log n).

Example 1

Input: nums = [3, 4, 5, 1, 2]
Output: 1

Example 2

Input: nums = [11, 13, 15, 17]
Output: 11

Constraints

  • 1 ≤ n ≤ 5000
  • Distinct

Pattern clues in the wording

  • → Rotated sorted array
  • → O(log n)

These clues point to Binary Search on an Index: In sorted data, check the middle and throw away the half that can't contain the answer.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int findMin(int[] nums) {
        return nums[0];
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
nums = [3,4,5,1,2]
1
2
nums = [4,5,6,7,0,1,2]
0
3
nums = [11,13,15,17]
11

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: compare with the right end · O(log n)
1

Optimal: compare with the right end

Time O(log n) Space O(1)

lo = 0, hi = n − 1; while lo < hi: if nums[mid] > nums[hi], lo = mid + 1; else hi = mid. Return nums[lo].

Approach 1
class Solution {
    public int findMin(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];
    }
}

Verdict: Works for rotated and non-rotated arrays.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Not rotated
  • One element
  • Minimum at the last index

Mistakes people make

  • Comparing with nums[lo] (ambiguous for a non-rotated array).

Interview

Follow-up questions

How does this help search for a target?