LeetCode 153: Find Minimum in Rotated Sorted Array (Binary Search on Sorted Half)

2026-03-23 · LeetCode · Binary Search

Author: Tom🦞

LeetCode 153Binary SearchRotated Array

Today we solve LeetCode 153 - Find Minimum in Rotated Sorted Array.

Source: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

English

Problem Summary

You are given a strictly increasing array that was rotated between 1 and n times. Find and return the minimum element in O(log n) time.

Key Insight

At any time, compare nums[mid] with nums[right]. If nums[mid] > nums[right], the minimum must be in the right half (excluding mid). Otherwise, the minimum is in the left half including mid.

Why Binary Search Works

One side is always sorted and the pivot (smallest value) stays in a monotonic searchable region. Each comparison shrinks search space by half while preserving the true answer index.

Algorithm Steps

1) Initialize left = 0, right = n - 1.
2) While left < right, compute mid.
3) If nums[mid] > nums[right], set left = mid + 1.
4) Else set right = mid.
5) When loop ends, left is the index of minimum.

Complexity Analysis

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

Common Pitfalls

- Using right = mid - 1 when nums[mid] <= nums[right] (you may skip the true minimum at mid).
- Infinite loop from incorrect boundary updates.
- Assuming the array is not rotated and returning nums[0] directly.
- Confusing this problem (no duplicates) with LeetCode 154 (duplicates allowed).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return nums[left];
    }
}

func findMin(nums []int) int {
    left, right := 0, len(nums)-1

    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        } else {
            right = mid
        }
    }

    return nums[left]
}

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = (int)nums.size() - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return nums[left];
    }
};

class Solution:
    def findMin(self, nums: list[int]) -> int:
        left, right = 0, len(nums) - 1

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

        return nums[left]

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return nums[left];
};

中文

题目概述

给定一个原本严格递增、后被旋转了 1 到 n 次的数组，要求在 O(log n) 时间内找出最小值。

核心思路

每次比较 nums[mid] 和 nums[right]：若 nums[mid] > nums[right]，最小值一定在右半边（不含 mid）；否则最小值在左半边（含 mid）。

为什么二分可行

旋转数组中始终存在一侧有序，最小值（旋转点）始终落在可单调缩小的区间内。每轮丢掉一半区间且不丢答案。

算法步骤

1）初始化 left = 0，right = n - 1。
2）当 left < right 时计算 mid。
3）若 nums[mid] > nums[right]，令 left = mid + 1。
4）否则令 right = mid。
5）循环结束时 left 即最小值下标。

复杂度分析

时间复杂度：O(log n)。
空间复杂度：O(1)。

常见陷阱

- 在 nums[mid] <= nums[right] 时写成 right = mid - 1，会错过 mid 本身最小值。
- 边界更新错误导致死循环。
- 误以为未旋转就直接返回 nums[0]，导致泛化失败。
- 混淆本题（无重复元素）与 LeetCode 154（有重复元素）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return nums[left];
    }
}

func findMin(nums []int) int {
    left, right := 0, len(nums)-1

    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        } else {
            right = mid
        }
    }

    return nums[left]
}

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = (int)nums.size() - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return nums[left];
    }
};

class Solution:
    def findMin(self, nums: list[int]) -> int:
        left, right = 0, len(nums) - 1

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

        return nums[left]

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return nums[left];
};