#25 · Binary Search

Find Minimum in Rotated Sorted Array

A sorted array of unique values was rotated an unknown number of times (for example [0,1,2,4,5,6,7] became [4,5,6,7,0,1,2]). Return its minimum element in O(log n) time.

MediumLeetCode

Active
Found
Window
Visited
Rejected

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Rotated sorted array

A rotation splits a sorted array into two ascending runs, with a single "drop" where the larger run meets the smaller one. The minimum is the element right after the drop (or the first element if there was no rotation).

Memory layout

A contiguous array: O(1) random access by index, which is what makes binary search possible.

Operation	Cost
access by index	O(1)
find the drop by scanning	O(n)
find the drop by binary search	O(log n)

Binary search on a predicate

Binary search needs a yes/no question that flips exactly once across the range. Here: "is nums[i] > nums[last]?" is true for the whole first run and false for the whole second run, so the minimum is the first index where the answer is false.

Memory layout

Three integers: left, right, mid. The window halves every iteration.

Operation	Cost
search	O(log n) time, O(1) space

Why it fits

Comparing nums[mid] with nums[right] tells which run mid is in, and therefore which half contains the drop, even though the array as a whole is not sorted.
Each comparison discards half of the window, so about log₂ n probes are enough: 20 for a million elements.
Comparing against the right end (not the left) avoids a special case for arrays that were not rotated at all.

Why alternatives degrade

Linear scan:: Correct but O(n); it ignores that the array is almost sorted, and the problem explicitly asks for O(log n).
Sort a copy:: O(n log n) time and O(n) space to find one number.
Standard binary search for a value:: There is no target to compare against; the minimum has to be found from the structure of the array.

Four approaches, from naive to production

1 · beginner

Scan every element

time O(n)space O(1)

Walk through the array keeping the smallest value seen so far.

int findMin(vector<int>& nums) {
    int mn = nums[0];
    for (int i = 1; i < (int)nums.size(); i++) {
        if (nums[i] < mn) mn = nums[i];
    }
    return mn;
}

public int findMin(int[] nums) {
    int min = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] < min) min = nums[i];
    }
    return min;
}

def find_min(nums):
    mn = nums[0]
    for i in range(1, len(nums)):
        if nums[i] < mn: mn = nums[i]
    return mn

function findMin(nums: number[]): number {
  let min = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] < min) min = nums[i];
  }
  return min;
}

Flaws & bottlenecks

Reads every element even though the array is nearly sorted.
Does not meet the O(log n) requirement.
Works for any array, so it uses none of the structure of the problem.

Interviewer cross-questions

Can you use the fact that the array was sorted before rotation?

Say: Yes. The only place the order breaks is the rotation point; finding it with a binary search needs just log n comparisons.

What if the array is not rotated?

Say: The minimum is the first element. Any correct solution must handle that case; the scan does it naturally.

What is the lower bound for an unsorted array?

Say: Ω(n): you must look at every element. The rotated-sorted guarantee is what makes sublinear search possible.

2 · intermediate

Scan until the order breaks

time O(n)space O(1)

Stop at the first position where nums[i] < nums[i − 1]: that is the rotation point and the minimum. If no such position exists, the first element is the minimum.

int findMin(vector<int>& nums) {
    for (int i = 1; i < (int)nums.size(); i++) {
        if (nums[i] < nums[i - 1]) return nums[i];
    }
    return nums[0];
}

public int findMin(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] < nums[i - 1]) return nums[i];
    }
    return nums[0];
}

def find_min(nums):
    for i in range(1, len(nums)):
        if nums[i] < nums[i - 1]: return nums[i]
    return nums[0]

function findMin(nums: number[]): number {
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] < nums[i - 1]) return nums[i];
  }
  return nums[0];
}

Flaws & bottlenecks

Still O(n) when the rotation point is near the end.
Relies on distinct elements: with duplicates the drop can be hidden by equal values (a plateau).
Does not use the sortedness to skip ahead.

Interviewer cross-questions

Why can you stop at the first drop?

Say: Both runs are ascending, and every element of the second run is smaller than every element of the first. The first descent therefore marks the start of the second run, which begins with the global minimum.

How could you find the drop faster?

Say: Probe the middle and compare with an end: that tells you which half contains the drop, so you can discard the other half: binary search.

What if there are duplicates?

Say: Then nums[mid] == nums[right] gives no information, and the search degrades to O(n) in the worst case (shrink right by one).

3 · advanced

Binary search against the right end

time O(log n)space O(1)

Compare nums[mid] with nums[right]. If mid is larger, the drop is to the right, so left = mid + 1. Otherwise the minimum is at mid or to its left, so right = mid.

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

public int findMin(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return nums[left];
}

def find_min(nums):
    left = 0
    right = len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]

function findMin(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return nums[left];
}

Flaws & bottlenecks

The two bounds are updated differently (mid + 1 versus mid): mixing them up causes an infinite loop or skips the answer.
Assumes distinct elements; with duplicates it can discard the minimum.
(left + right) / 2 can overflow a fixed-width integer for very large arrays in some languages.

Interviewer cross-questions

Why compare with nums[right] and not nums[left]?

Say: nums[right] is always in the second run (or the last element of a sorted array), so "nums[mid] > nums[right]" cleanly means mid is in the first run. Comparing with nums[left] is ambiguous when the array is not rotated.

Why right = mid and not mid − 1?

Say: When nums[mid] ≤ nums[right], mid can itself be the minimum. Discarding it would lose the answer, so it stays in the window.

How do duplicates change it?

Say: If nums[mid] == nums[right] you cannot tell which side holds the drop, but you can safely do right−−. That keeps correctness and makes the worst case O(n).

4 · expert

Early exit + overflow-safe midpoint

time O(log n)space O(1)

The same search, plus: if nums[left] < nums[right] the window is sorted and its first element is the answer, so return at once. The midpoint is computed as left + (right − left) / 2.

int findMin(vector<int>& nums) {
    int left = 0;
    int right = (int)nums.size() - 1;
    while (left < right) {
        if (nums[left] < nums[right]) return nums[left];
        int mid = left + ((right - left) >> 1);
        if (nums[mid] >= nums[left]) left = mid + 1;
        else right = mid;
    }
    return nums[left];
}

public int findMin(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        if (nums[left] < nums[right]) return nums[left];
        int mid = left + ((right - left) >> 1);
        if (nums[mid] >= nums[left]) left = mid + 1;
        else right = mid;
    }
    return nums[left];
}

def find_min(nums):
    left = 0
    right = len(nums) - 1
    while left < right:
        if nums[left] < nums[right]: return nums[left]
        mid = left + ((right - left) >> 1)
        if nums[mid] >= nums[left]: left = mid + 1
        else: right = mid
    return nums[left]

function findMin(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    if (nums[left] < nums[right]) return nums[left];
    const mid = left + ((right - left) >> 1);
    if (nums[mid] >= nums[left]) left = mid + 1;
    else right = mid;
  }
  return nums[left];
}

Flaws & bottlenecks

Compares with nums[left] inside the loop, which adds one comparison per iteration for the early exit (usually only worth it when many inputs are not rotated).
Still assumes distinct values: a window like [2,2,2,0,2] defeats both comparisons.
The ≥ in the mid test is subtle: it is what handles mid == left; using > loops forever on two-element windows.

Interviewer cross-questions

Why left + (right − left) / 2?

Say: left + right can exceed the maximum integer for huge arrays in fixed-width languages (a famous bug in many standard libraries). The subtraction form never overflows.

When does the early exit help?

Say: When the array is not rotated, or after the window has narrowed to a sorted piece: the loop ends immediately. It never hurts correctness: a sorted window always has its minimum at left.

Why is ≥ needed in nums[mid] >= nums[left]?

Say: When the window has two elements, mid equals left. Then nums[mid] == nums[left] and the minimum can only be to the right. With a strict > the code would pick right = mid and never shrink.

Synchronized code walkthrough

Showing: Scan every element — shares the player above; click any step to jump.

int findMin(vector<int>& nums) {
    int mn = nums[0];
    for (int i = 1; i < (int)nums.size(); i++) {
        if (nums[i] < mn) mn = nums[i];
    }
    return mn;
}

public int findMin(int[] nums) {
    int min = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] < min) min = nums[i];
    }
    return min;
}

def find_min(nums):
    mn = nums[0]
    for i in range(1, len(nums)):
        if nums[i] < mn: mn = nums[i]
    return mn

function findMin(nums: number[]): number {
  let min = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] < min) min = nums[i];
  }
  return min;
}

int findMin(vector<int>& nums) {
    for (int i = 1; i < (int)nums.size(); i++) {
        if (nums[i] < nums[i - 1]) return nums[i];
    }
    return nums[0];
}

public int findMin(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] < nums[i - 1]) return nums[i];
    }
    return nums[0];
}

def find_min(nums):
    for i in range(1, len(nums)):
        if nums[i] < nums[i - 1]: return nums[i]
    return nums[0]

function findMin(nums: number[]): number {
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] < nums[i - 1]) return nums[i];
  }
  return nums[0];
}

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

public int findMin(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return nums[left];
}

def find_min(nums):
    left = 0
    right = len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]

function findMin(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return nums[left];
}

int findMin(vector<int>& nums) {
    int left = 0;
    int right = (int)nums.size() - 1;
    while (left < right) {
        if (nums[left] < nums[right]) return nums[left];
        int mid = left + ((right - left) >> 1);
        if (nums[mid] >= nums[left]) left = mid + 1;
        else right = mid;
    }
    return nums[left];
}

public int findMin(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        if (nums[left] < nums[right]) return nums[left];
        int mid = left + ((right - left) >> 1);
        if (nums[mid] >= nums[left]) left = mid + 1;
        else right = mid;
    }
    return nums[left];
}

def find_min(nums):
    left = 0
    right = len(nums) - 1
    while left < right:
        if nums[left] < nums[right]: return nums[left]
        mid = left + ((right - left) >> 1)
        if nums[mid] >= nums[left]: left = mid + 1
        else: right = mid
    return nums[left]

function findMin(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    if (nums[left] < nums[right]) return nums[left];
    const mid = left + ((right - left) >> 1);
    if (nums[mid] >= nums[left]) left = mid + 1;
    else right = mid;
  }
  return nums[left];
}