AlgoViz
HomeBinary Search

Find minimum in Rotated Sorted Array

Easy

Compare mid with the right end

Problem

Given an integer array nums of size N, sorted in ascending order with distinct values, and then rotated an unknown number of times (between 1 and N), find the minimum element in the array.

In simple words

Compare mid with the right end to decide which half holds the wrap-around minimum.

The idea

In a rotated sorted array exactly one half is properly sorted. Comparing nums[mid] with nums[hi] tells you which side the rotation point lies on, so you can discard the sorted half and keep halving.

The trick

  • nums[mid] > nums[hi] means the minimum is strictly right of mid.
  • Otherwise the minimum is at mid or to its left — set hi = mid, not mid - 1.
  • Comparing against hi rather than lo handles the unrotated case for free.
4
5
6
7
0
1
2
0
1
2
3
4
5
6
min4

Step 1 of 8. Brute force: scan the whole array, remembering the smallest. Values: 4, 5, 6, 7, 0, 1, 2. min 4.

1/8
Brute force
timeO(n)spaceO(1)

Scan for the min.

1// scan the whole array, remembering the smallest2for (let i = 1; i < n; i++)3  if (nums[i] < min) min = nums[i];4return min;

Input

array
[4, 5, 6, 7, 0, 1, 2]

Memory

i
—

Output

min
4
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [3, 4, 5, 1, 2]
Output:
1
Explanation:
The rotation point holds the min, 1.

Example 2

Input:
nums = [4, 5, 6, 7, 0, 1, 2]
Output:
0
Explanation:
0 is the smallest.

Example 3

Input:
nums = [11, 13, 15, 17]
Output:
11
Explanation:
Not rotated → first element.

Constraints

  • n == nums.length
  • 1 <= n <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • All the integers of nums are unique.
  • nums is sorted and rotated between 1 and n times.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.