Coding interview problems › Binary Search

🔍 Binary Search Medium

Find Minimum in Rotated Sorted Array

Find Minimum in Rotated Sorted Array: compare mid with the right end to binary search the rotation point in O(log n). Tested Python code, pitfalls, live visual.

Also searched as: find rotation point in sorted array · minimum of rotated array binary search · how many times is a sorted array rotated

🔍

Try it live Free

Binary Search

Practise the halving loop in the binary search lab and pay attention to the lab's off-by-one traps: here the else branch must keep mid (hi = mid), which is exactly that kind of boundary choice.

Open the playground →

The problem

A sorted list of distinct integers was rotated some number of times, for example [3, 5, 7, 9, 1, 2]. Return its smallest element in O(log n) time.

Inputnums = [3, 5, 7, 9, 1, 2]
Output1
Inputnums = [10, 20, 30]
Output10

Not rotated at all.

The key insight

Compare the middle element with the last element. If nums[mid] > nums[hi], the drop (and the minimum) must be to the right of mid. Otherwise the stretch from mid to hi is sorted, so the minimum is mid itself or something to its left. Shrink towards the drop until one element remains.

Brute force first: Calling min(nums) or scanning for the place where a value is smaller than its left neighbour takes O(n).

Step-by-step approach

  1. Set lo = 0, hi = len(nums) - 1.
  2. While lo < hi, compute mid = (lo + hi) // 2.
  3. If nums[mid] > nums[hi], the minimum is strictly right of mid: lo = mid + 1.
  4. Otherwise mid might be the minimum: hi = mid.
  5. When lo == hi, return nums[lo].

Python solution

PYTHON 3tested
def find_min(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:    # the drop is to the right of mid
            lo = mid + 1
        else:                       # mid..hi is sorted, min is at mid or left
            hi = mid
    return nums[lo]

Complexity

TimeO(log n)
SpaceO(1)

Each comparison discards about half of the range and the minimum is never discarded, so O(log n) iterations with constant extra space.

Common mistakes

Frequently asked questions

What is the time and space complexity?

O(log n) time and O(1) extra space.

How do I get the number of rotations?

The index of the minimum, lo when the loop ends, equals how many positions the sorted array was rotated to the right.

What if there are duplicates?

When nums[mid] equals nums[hi] you cannot decide which side holds the minimum, so decrement hi by one and continue. That keeps the answer correct but makes the worst case O(n).

Why compare with the right end rather than the left?

The right end works for every case including an unrotated array: if nums[mid] is not greater than nums[hi], mid to hi is sorted. Comparing with the left end needs an extra check for the unrotated case.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Binary Search Binary Search lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.