面试题11：旋转数组的最小数字

从有序数组被切成两段开始

先预测：数组[3,4,5,1,2]的中间元素5大于首项3，它更可能位于最小值之前还是之后？若数组变成[1,0,1,1,1]，首项、中间项、末项都是1，同样的比较还能告诉我们0在哪一侧吗？

题目把非递减排序数组最开始的若干元素搬到末尾，这个操作称为旋转。例如[1,2,3,4,5]旋转前3项得到[4,5,1,2,3]。要求找出旋转数组的最小数字，不是恢复原数组，也不是寻找任意局部下降点。

旋转后通常形成：前段来自原数组后缀，后段来自原数组前缀。书中沿用“递增”表述，但官方测试允许重复元素，严格说应理解为非递减。最小值位于第二段起点，也就是。

旋转0个元素也是合法输入，此时数组保持整体有序，只有一段，首项就是最小值。单元素数组同样满足这个规则。算法不能假定一定存在明显的“前项大于后项”断裂。

用两个边界夹住旋转点

作者算法维护闭区间[index1,index2]。在典型旋转状态中，index1位于第一段，index2位于第二段，最小值始终落在两者之间；当两个下标相邻时，index2就是第二段起点，即答案。

每轮取中点indexMid。若中间值大于等于左边界值，中点位于第一段，最小值不会在中点左侧，可令index1=indexMid；若中间值小于等于右边界值，中点位于第二段，中点本身可能是最小值，所以令index2=indexMid，不能写成indexMid+1。

这种每轮排除一半候选区间的策略是。它与在完整有序数组中查目标值的二分不同：这里查的是两段边界，左右下标更新方式由“中点属于哪一段”决定。

作者把indexMid初始为index1，并仅在numbers[index1] >= numbers[index2]时进入循环。若首值小于末值，说明当前区间整体非递减，循环不执行，直接返回首项；这正好处理未旋转数组。

按作者边界规则实现

下面保留作者的闭区间不变量，同时使用std::span表达非空连续输入，按值抛出异常。辅助函数只在比较证据消失时扫描当前候选区间。

#include <span>
#include <stdexcept>
 
int minInOrder(std::span<const int> numbers,
               std::size_t left,
               std::size_t right) {
    int result = numbers[left];
    for (std::size_t i = left + 1; i <= right; ++i) {
        if (numbers[i] < result) result = numbers[i];
    }
    return result;
}
 
int minInRotatedArray(std::span<const int> numbers) {
    if (numbers.empty()) {
        throw std::invalid_argument("numbers must not be empty");
    }
 
    std::size_t left = 0;
    std::size_t right = numbers.size() - 1;
    std::size_t middle = left;
 
    while (numbers[left] >= numbers[right]) {
        if (right - left == 1) {
            middle = right;
            break;
        }
 
        middle = left + (right - left) / 2;
        if (numbers[left] == numbers[middle] &&
            numbers[middle] == numbers[right]) {
            return minInOrder(numbers, left, right);
        }
 
        if (numbers[middle] >= numbers[left]) {
            left = middle;
        } else if (numbers[middle] <= numbers[right]) {
            right = middle;
        }
    }
    return numbers[middle];
}

left + (right-left)/2比(left+right)/2更稳妥，可避免大下标相加溢出。由于left与right都是无符号下标，只有在保证right >= left时才能做差；这里的区间不变量提供该保证。

作者源码在非法输入时throw new std::exception(...)，这会抛出裸指针，调用方按catch(const std::exception&)无法捕获且还涉及释放责任。现代 C++ 应按值抛std::invalid_argument、返回optional，或在接口类型上禁止空输入。

三点相等为何必须退化

考虑官方输入[1,0,1,1,1]：左边界、中点、右边界的值都等于1。中间的1可能属于最小值之前的第一段，也可能属于最小值之后的第二段，仅凭三次取值无法判断0在左侧还是右侧。若机械执行“中值大于等于左值就丢左半边”，会把真正答案0排除。

因此作者规定：首尾和中间元素相等时顺序查找当前区间。牺牲速度换取正确性。

也可以使用更常见的右边界比较版本：中值大于右值时最小值在右半边，中值小于右值时最小值在包含中点的左半边，中值等于右值时只把right减一。最后一个动作一次仅排除一个与中值相同的右端元素，仍可能退化到O(n)，但无需单独辅助扫描。

int minByRightBoundary(std::span<const int> numbers) {
    if (numbers.empty()) {
        throw std::invalid_argument("empty array");
    }
    std::size_t left = 0;
    std::size_t right = numbers.size() - 1;
 
    while (left < right) {
        const auto middle = left + (right - left) / 2;
        if (numbers[middle] > numbers[right]) {
            left = middle + 1;
        } else if (numbers[middle] < numbers[right]) {
            right = middle;
        } else {
            --right;
        }
    }
    return numbers[left];
}

numbers[middle] < numbers[right]时保留中点，因为它可能就是最小值；numbers[middle] > numbers[right]时中点确定在前段，最小值严格在其右侧，才使用middle+1。两个分支边界不同是由“中点是否仍可能为答案”决定的。

相等分支中的--right也不是随意删元素。若numbers[middle] == numbers[right]且右端恰是某个最小值，那么中点拥有相同数值，删除右端仍至少保留一个同值最小候选；若右端不是最小值，删除它当然不会丢答案。它只能保证“最小值这个数仍在区间”，不能保证保留原数组中某个指定最小值下标。

因此两种重复值策略的语义略有不同。作者顺序扫描直接返回最小数值；右端递减版最后也返回最小数值。若接口要求“旋转点的唯一原下标”，重复最小值可能跨越数组首尾，例如[1,1,2,1]中数值1出现多个位置，仅凭最小值定义没有唯一答案。必须额外约定返回第二段起点、最左最小值、最右最小值或任意最小值，再为该约定设计边界。

正确性来自候选区间不丢答案

初始区间包含整个数组，显然包含最小值。未旋转时首值小于末值，首项最小；旋转状态下，第一段元素整体不小于第二段，左右边界跨在旋转点两侧。

中点落在第一段时，它左侧仍属于第一段，不可能包含第二段起点，所以移动左边界不会丢答案。中点落在第二段时，最小值可能等于中点或在其左侧，移动右边界到中点继续保留答案。边界相邻时，中间再无其他位置，右边界就是第二段第一项。三点相等则不作无依据排除，改用完整扫描。

无重复值或每轮都能判断中点所属段时，候选长度约减半，时间O(log n)、空间O(1)。大量重复值会让每轮只能删一个端点或直接扫描，最坏O(n)。这不是实现失败，而是相等观测无法提供足够信息。

输入必须确实是某个非递减数组的旋转。任意乱序数组不满足两段结构，二分结论失去依据。若接口需要验证前提，必须线性检查下降次数和首尾关系，这会让整体最坏时间本来就是O(n)；常见题目把合法性作为调用前置条件。

找最小值与查找目标值不要混用边界

在旋转数组中查给定目标值是相关但不同的问题。找最小值只需判断中点属于旋转点哪一侧；查目标值还要先识别哪一半完整有序，再判断目标是否落在该半区的值域内。把“目标在左段还是右段”的条件搬进本题，会引入一个根本不存在的目标参数，也容易错误越过中点。

反过来，本题的right=middle也不能原样套入普通目标查找。这里中点可能就是最小值，所以必须保留；普通查找已经比较出中点不等于目标时，可以排除中点。二分模板不是固定的left=mid+1与right=mid-1组合，每个加一或不加一都应由“中点还能否成为答案”证明。

寻找下降对则是另一个线性基线：扫描到numbers[i] > numbers[i+1]时，i+1是第二段起点；若扫描结束没有下降，最小值在下标0。它对合法输入简单可靠，适合作为测试预言机，也适合数据很小或需要同时验证输入时使用。二分方案的价值是在比较可提供方向证据时跳过整段元素。

对批量查询，同一只读数组可以先求出旋转点，然后把任何目标查找映射回两个有序区间；对只查询一次最小值，预处理没有收益。算法选择不仅取决于n，还取决于数组是否复用以及调用方究竟需要数值、下标还是合法性报告。

官方七类测试如何卡住边界

作者测试[3,4,5,1,2]得到1，覆盖标准旋转；[3,4,5,1,1,2]覆盖最小值重复；[3,4,5,1,2,2]覆盖非边界重复；[1,0,1,1,1]覆盖首尾中点三值相等的退化。

[1,2,3,4,5]验证旋转0项时返回首项，[2]验证单元素，空指针加长度0验证非法输入。更完整的现代测试还应加入全相等数组、两元素旋转、最小值在末尾、负数、重复最小值跨旋转边界，以及随机生成有序数组再旋转后与std::min_element交叉验证。

#include <algorithm>
#include <array>
#include <cassert>
 
void testOfficialCases() {
    const std::array a1{3, 4, 5, 1, 2};
    const std::array a2{3, 4, 5, 1, 1, 2};
    const std::array a3{3, 4, 5, 1, 2, 2};
    const std::array a4{1, 0, 1, 1, 1};
    const std::array a5{1, 2, 3, 4, 5};
    const std::array a6{2};
 
    assert(minInRotatedArray(a1) == 1);
    assert(minInRotatedArray(a2) == 1);
    assert(minInRotatedArray(a3) == 1);
    assert(minInRotatedArray(a4) == 0);
    assert(minInRotatedArray(a5) == 1);
    assert(minInRotatedArray(a6) == 2);
}
 
void testAgainstLinearOracle(std::span<const int> values) {
    assert(minInRotatedArray(values) ==
           *std::min_element(values.begin(), values.end()));
}

性质测试生成器应先产生非递减数组，再选择0到n-1的切口执行旋转，这样每个随机样例都满足题目契约。直接生成任意数组会把非法输入混入，失败时无法区分算法错误和前置条件破坏。

本章练习

概念说明

本章核心概念包括：两个递增子数组，首尾和中间元素相等时顺序查找。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

1. 旋转数组由原非递减数组的后缀和前缀拼接，形成两个递增子数组。
2. 旋转点是第二段起点，也是旋转数组的最小数字。
3. 二分查找通过中点与边界关系判断它属于哪一段，并保留最小值候选区间。
4. 左右边界相邻时，右边界就是最小元素位置。
5. 未旋转数组首值小于末值，初始中点保持在首项并直接返回。
6. 首尾和中间元素相等时顺序查找，否则可能错误排除包含最小值的一侧。
7. 一般时间为O(log n)、空间O(1)，重复值最坏退化为O(n)。
8. 输入必须是非递减数组的合法旋转；验证这一前提本身需要线性工作。

名词解释