LeetCode 剑指 Offer 11. 旋转数组的最小数字

Categories:

题目描述
思路分析
1. 解法一：二分查找（推荐）
相似题目

题目描述

✅ 剑指 Offer 11. 旋转数组的最小数字

思路分析

解法一：二分查找（推荐）

核心思路：

旋转数组可能含有重复元素，始终用 nums[mid] 与 nums[right] 比较来确定最小值所在区间。

若 nums[mid] < nums[right]：最小值在 [left, mid] 区间，收缩右边界：right = mid。

若 nums[mid] > nums[right]：最小值在 [mid+1, right] 区间，收缩左边界：left = mid + 1。

若 nums[mid] == nums[right]：无法判断最小值位置，但可以安全地将 right--（排除一个重复值），缩小搜索范围。

循环结束时，left == right，即为最小值的下标。

复杂度分析：

时间复杂度：O(log n)，最坏情况（全部元素相同）退化为 O(n)，其中 n 为数组长度。

空间复杂度：O(1)，仅使用常数级额外空间。

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

        while (left < right) {
            int mid = left + (right - left) / 2;

            // 最小值在左半部分，缩小右边界
            if (numbers[mid] < numbers[right]) {
                right = mid;
            // 最小值在右半部分，缩小左边界
            } else if (numbers[mid] > numbers[right]) {
                left = mid + 1;
            // 无法判断，安全地缩小右边界排除重复值
            } else {
                right--;
            }
        }

        return numbers[left];
    }
}

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

	for left < right {
		mid := left + (right-left)/2

		// 最小值在左半部分，缩小右边界
		if numbers[mid] < numbers[right] {
			right = mid
		// 最小值在右半部分，缩小左边界
		} else if numbers[mid] > numbers[right] {
			left = mid + 1
		// 无法判断，安全地缩小右边界排除重复值
		} else {
			right--
		}
	}

	return numbers[left]
}

相似题目

题目	难度	考察点
153. 寻找旋转排序数组中的最小值	中等	二分查找、旋转数组
154. 寻找旋转排序数组中的最小值 II	困难	二分查找、旋转数组
33. 搜索旋转排序数组	中等	二分查找、旋转数组
81. 搜索旋转排序数组 II	中等	二分查找、旋转数组
162. 寻找峰值	中等	二分查找
852. 山脉数组的峰顶索引	中等	二分查找
剑指 Offer 04. 二维数组中的查找	中等	二分查找、矩阵

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/32286965