LeetCode 面试题 10.03. 搜索旋转数组

2025-08-28 HGNULB 约 6 分钟

文章信息 12 个分类 · 2 个标签

分类

LeetCode CodeTop 中等 未解决 10-20 程序员面试金典（第 6 版） 字节 微软 美团 小米 百度 滴滴

标签

数组 二分查找

题目描述

✅ 面试题 10.03. 搜索旋转数组

题意分析

数组原本非递减，旋转后最多出现一处从大到小的断点。要查找 target，不存在时返回 -1；存在重复值时，必须返回它在当前数组中的最小下标。

普通二分依赖整个区间有序，本题只能先判断哪一半有序，再通过该半区的取值范围排除元素。重复值可能使断点的位置无法判断，此时不能强行砍掉一半；中点命中也不能直接返回，因为左边可能还有目标。

解法：含重复元素的旋转二分

核心思路

[!blue]

left、right 表示当前候选闭区间。始终保证：left 之前没有目标；如果目标存在，它的最小下标还在 [left, right] 中。因此每轮先检查 arr[left]，命中时就能立即返回。

如果 arr[mid] == target，最早出现的位置只能在 [left, mid] 中，令 right = mid 保留这个已知答案，并继续查找更小下标。左端已经检查过，所以此时 mid > left，区间仍会缩小。

中点不命中时，比较 arr[left] 与 arr[mid]：

• arr[left] < arr[mid]：左半区没有跨过断点，因而有序。目标落在两端值之间，就保留左半区；否则左半区没有目标，可以整体丢弃。两个端点已确认不等于目标，所以范围两端都用严格不等号。
• arr[left] > arr[mid]：断点已经出现在左半区，右半区必定有序。目标满足 arr[mid] < target <= arr[right] 时保留右半区。此时左半区断点前的值不小于 arr[left]，断点后的值不大于 arr[mid]；右段的值又不大于 arr[left]，且左端已经排除，因此不会漏掉左半区中更早的目标。目标不在这个范围内时，丢弃右半区。
• arr[left] == arr[mid]：相等的端点无法揭示中间是否有断点。但 arr[left] 已确认不是目标，所以只执行 left++，安全排除这一个位置。

每种分支都保留最早的目标，同时让区间缩小。最终左端命中即得到答案；区间变空则说明目标不存在。

解题步骤

• 初始化闭区间 [left, right]，循环条件为 left <= right；空数组会直接返回 -1。
• 每轮先检查左端点。若 arr[left] == target，根据不变量它就是全局最小下标。
• 若中点命中，令 right = mid 继续向左找。此时 mid > left，所以区间一定缩小。
• 若 arr[mid] > arr[left]，说明 [left, mid] 有序：target 落在 (arr[left], arr[mid]) 之间才可能在左半边，于是 right = mid - 1；否则 left = mid + 1。
• 若 arr[mid] < arr[left]，说明旋转点在 (left, mid]，[mid, right] 有序：target 落在 (arr[mid], arr[right]] 之间才可能在右半边，于是 left = mid + 1；否则 right = mid - 1。注意右端要取闭区间 <=，否则会漏掉恰好等于 arr[right] 的目标。
• 若 arr[left] == arr[mid]，执行 left++ 消除重复值造成的歧义。
• 循环结束仍未命中，返回 -1。

代码实现

class Solution {
    public int search(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            // 左端点命中即是最小下标，区间左侧已被证明不含 target。
            if (arr[left] == target) {
                return left;
            }

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

            if (arr[mid] == target) {
                // 左边可能还有更早的出现位置，只收缩右边界。
                right = mid;
            } else if (arr[mid] > arr[left]) {
                if (arr[left] < target && target < arr[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else if (arr[mid] < arr[left]) {
                if (arr[mid] < target && target <= arr[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                // 重复值遮蔽有序区间时，只能安全地丢掉一个左端点。
                left++;
            }
        }

        return -1;
    }
}

func search(arr []int, target int) int {
    left := 0
    right := len(arr) - 1
    for left <= right {
        // 左端点命中即是最小下标。
        if arr[left] == target {
            return left
        }

        mid := left + (right-left)/2
        if arr[mid] == target {
            // 继续向左找更小的下标。
            right = mid
        } else if arr[mid] > arr[left] {
            if arr[left] < target && target < arr[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else if arr[mid] < arr[left] {
            if arr[mid] < target && target <= arr[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        } else {
            // 无法判断有序侧，只丢掉一个左端点。
            left++
        }
    }
    return -1
}

复杂度分析

• 时间复杂度：每轮都能判断有序侧时为 $O(\log n)$；最坏为 $O(n)$，因为相等分支每次只排除一个元素。数组全相等而目标不存在时，就会出现这种退化。
• 空间复杂度：$O(1)$，只用了 left、right、mid 三个下标变量，没有递归也没有额外容器。

关键点总结

[!green]

• 本题必须返回最小下标，这是它区别于 33、81 的核心考点；命中 mid 时收缩右边界而不是直接返回，是解法的关键改动。
• 循环开头的 arr[left] == target 检查一举两得：既让返回值天然最小，又为「arr[left] == arr[mid] 时 left++」提供了安全性依据。
• 只有证明被丢弃的左半区没有目标，才能移动 left；缩小 right 时则必须保留可能的最早目标。
• 重复元素会遮蔽有序半区的判断，此时只能排除已确认不等于目标的左端，最坏复杂度因此退化。

易错点总结

[!yellow]

• 中点命中就返回，会漏掉左边下标更小的相同元素；应保留中点并继续向左找。
• 保留 right=mid 却删掉左端命中检查，收缩到命中单点时可能不再前进。
• 左端与中点相等就跨过半区，可能漏掉中间藏着的目标；只能保守移一格。
• 判断右侧有序段时要包含右端值，目标可能恰好等于 arr[right]。
• 重复值使最坏复杂度线性，不能保证每次都能排除一半。

相似题目

题目	难度	关联与区别
81. 搜索旋转排序数组 II	中等	同样允许旋转数组含重复值，原题只返回是否存在，本题必须返回最小下标，命中后不能直接忽略更左候选。
33. 搜索旋转排序数组	中等	无重复值时判断有序半区更直接，本题重复元素会遮蔽边界并影响最早位置的选择。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2025/53346308

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！