面试题53（三）：数组中数值和下标相等的元素

从“3为什么同时是值和位置”开始

先预测：在-3、-1、1、3、5中，哪个元素的数值恰好等于自己的下标？下标从0开始，逐项对齐后可以看到numbers[3]等于3。这个满足numbers[i]等于i的位置称为不变点。

题目要求在一个单调递增数组中找到任意一个数组中数值和下标相等的元素。所有数字都是整数且互不相同，所以这里的递增不是允许重复的非递减，而是严格递增。

线性扫描逐个比较当然能找到答案，时间O(n)。作者进一步观察值与下标的相对大小，让每次比较都能排除一半区间，把时间降为O(log n)。

图中数值减下标依次为-3、-2、-1、0、1。差为0的位置就是答案；负差说明当前值落在下标之下，正差说明当前值超过下标。

差值为什么不会下降

定义第i项的差为numbers[i]减i。因为数组是严格递增的整数序列，numbers[i加1]至少比numbers[i]大1；与此同时，下标也恰好增加1。因此下一项差减去当前差至少为0。

这些差组成。它可能保持不变，也可能一次跳过0，但不会先变正再回到负数。

“严格递增数组”与“差值严格递增”不是一回事。若原数组连续增加1，例如0、1、2，差值会连续保持0，因此可以同时存在多个答案。作者函数只要求返回任意一个，不要求最左或最右。

如果允许重复，差值就可能下降。例如0、0的差值是0、-1，原本的单调性被破坏。旧页声称需要处理重复值并不符合作者题目；源码注释明确要求每个元素唯一。

三种比较如何决定方向

作者每轮都在闭区间left到right中取middle，然后比较numbers[mid]与mid。

若numbers[middle]等于middle，已经找到合法不动点，立即返回。

若numbers[middle]大于middle，考虑任意右侧下标j。严格递增整数保证从middle走到j时，数值至少增加j减middle，所以numbers[j]至少等于numbers[middle]加j减middle。由于middle处已经比下标大，右侧每一项也都会比自己的下标大，答案不可能在middle右侧。可以执行。

若numbers[middle]小于middle，镜像地看左侧任意下标j。向左每一步数值至少减少1，因此numbers[j]仍会小于j，答案不可能在middle左侧。可以执行。

这就是“二分排除一半区间”的完整证明。仅凭“数组有序”四个字还不够；真正使用的是严格递增整数带来的步长下界。

忠实还原作者代码

作者入口先拒绝空指针和非正长度。中点用left加区间长度的一半，已经避开left与right直接相加的溢出风险。

int GetNumberSameAsIndex(
    const int* numbers,
    int length) {
    if (numbers == nullptr ||
        length <= 0) {
        return -1;
    }
 
    int left = 0;
    int right = length - 1;
    while (left <= right) {
        int middle =
            left +
            ((right - left) >> 1);
 
        if (numbers[middle] == middle) {
            return middle;
        }
 
        if (numbers[middle] > middle) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
    return -1;
}

循环每轮要么返回，要么让搜索区间至少缩小一半。若区间变空仍未命中，返回-1。算法只维护三个下标变量，时间O(log n)，额外空间O(1)，输入由const指针只读访问。

手算作者第1组用例

数组为-3、-1、1、3、5，初始区间0到4。middle为2，numbers[2]等于1，小于下标2。根据左半排除，0到2都不可能有解，令left等于3。

第二轮区间3到4，middle为3，numbers[3]等于3，直接返回3。

这里的分支名称容易说反：当前值小于下标时，答案应向右找；当前值大于下标时，答案应向左找。可用差值符号记忆，但面试中仍应给出严格递增推导，而不是靠口诀。

多个答案时返回哪一个

作者第2组数组0、1、3、5、6同时满足numbers[0]等于0和numbers[1]等于1。函数并不承诺最小下标，它按当前二分路径返回首先命中的解。

初始middle为2，numbers[2]等于3，大于2，于是right改为1。下一轮middle为0并命中，所以作者测试期望0。若采用向上取整中点，完全可能先命中1；从题意“找到任意一个”看也正确，但会与作者这组精确返回值测试不同。

所有零差值必然构成连续区间。因为差值序列不下降，一旦从0变成正数就不会再回到0。要找最左解，可以在命中时记录middle并继续缩小右边界。

int GetFirstNumberSameAsIndex(
    const int* numbers,
    int length) {
    if (numbers == nullptr ||
        length <= 0) {
        return -1;
    }
 
    int left = 0;
    int right = length - 1;
    int answer = -1;
    while (left <= right) {
        const int middle =
            left + (right - left) / 2;
        if (numbers[middle] >= middle) {
            if (numbers[middle] == middle) {
                answer = middle;
            }
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
    return answer;
}

这个扩展把谓词改为numbers[i]大于或等于i，寻找第一次为真，再确认该位置是否恰好相等。它不是作者原函数，只用于说明“任意命中”和“边界搜索”的语义差异。

无解并不要求差值永远同号

数组-1、0、1、2、5的差值是-1、-1、-1、-1、1。差值从负数直接跳到正数，没有出现0，所以返回-1。

二分无需先确认差值是否跨过0。落在负差就向右，落在正差就向左；最终闭区间变空。这个过程同时覆盖“全为负差”“全为正差”和“跳过0”三种无解形态。

若数组首元素已经大于0，所有后续差值都不小于它，可直接判断无解；若末元素仍小于末下标，也可直接判断无解。这些只是可选的常数级提前退出，不改变复杂度，作者没有加入。

输入契约与边界

负数完全合法。下标始终非负，但负前缀会自然产生负差，推动搜索向右。作者第1、3、4组都用负数开头，证明实现没有把数值误当成数组下标访问。

空指针或length小于等于0时返回-1，不进入循环。非空指针配0长度同样返回-1。与上一小题相同，length必须真实反映可读元素个数；若调用方谎报更大长度，源码可能越界读取，函数自身无法校验内存边界。

作者已用left加right减left的一半计算中点，避免了两个大正下标直接相加。right减left在循环条件left不大于right时非负。长度和下标仍使用int，因此接口不适合元素数超过int范围的容器；现代C++可使用span与size_t。

#include <cstddef>
#include <optional>
#include <span>
 
std::optional<std::size_t>
findValueEqualToIndex(
    std::span<const int> numbers) {
    std::size_t left = 0;
    std::size_t right = numbers.size();
 
    while (left < right) {
        const std::size_t middle =
            left + (right - left) / 2;
        const long long value =
            numbers[middle];
        const long long index =
            static_cast<long long>(middle);
 
        if (value == index) {
            return middle;
        }
        if (value > index) {
            right = middle;
        } else {
            left = middle + 1;
        }
    }
    return std::nullopt;
}

半开区间版本用optional区分“无解”与合法下标0，不再借用-1哨兵。比较时转为更宽有符号类型，避免size_t与负数混合比较导致负值被转换成巨大无符号数。

作者7组测试逐项还原

1. -3、-1、1、3、5，命中中间下标3，期望3。
2. 0、1、3、5、6，有下标0和1两个解，作者路径返回0。
3. -1、0、1、2、4，命中最后下标4，期望4。
4. -1、0、1、2、5，差值从负跳到正，无解，期望-1。
5. 单元素0在下标0命中，期望0。
6. 单元素10不等于下标0，期望-1。
7. nullptr与长度0，入口拒绝，期望-1。

第2组是最容易被简化摘要漏掉的测试。它证明合法输入可以有多个答案，也证明作者测试不仅检查“结果是某个合法位置”，而是固定期望当前实现返回0。

下面先逐项复现作者测试，再对随机严格递增数组与线性扫描对拍。因为任意解都合法，对拍不能简单要求两个函数返回完全相同的下标；应检查二分返回-1时线性也无解，返回非负时该位置确实满足值等于下标。

#include <cassert>
 
bool hasAnyMatch(
    const int* numbers,
    int length) {
    for (int i = 0; i < length; ++i) {
        if (numbers[i] == i) {
            return true;
        }
    }
    return false;
}
 
void testIntegerIdenticalToIndex() {
    int middle[] = {-3, -1, 1, 3, 5};
    int multiple[] = {0, 1, 3, 5, 6};
    int last[] = {-1, 0, 1, 2, 4};
    int none[] = {-1, 0, 1, 2, 5};
    int zero[] = {0};
    int ten[] = {10};
 
    assert(GetNumberSameAsIndex(
        middle, 5) == 3);
    assert(GetNumberSameAsIndex(
        multiple, 5) == 0);
    assert(GetNumberSameAsIndex(
        last, 5) == 4);
    assert(GetNumberSameAsIndex(
        none, 5) == -1);
    assert(GetNumberSameAsIndex(
        zero, 1) == 0);
    assert(GetNumberSameAsIndex(
        ten, 1) == -1);
    assert(GetNumberSameAsIndex(
        nullptr, 0) == -1);
 
    const int result =
        GetNumberSameAsIndex(multiple, 5);
    assert(result == -1 ||
           multiple[result] == result);
    assert((result != -1) ==
           hasAnyMatch(multiple, 5));
}

随机数据生成器必须确保每个新值严格大于前一个值，可随机增加1到若干步。若直接独立生成后排序，重复值仍可能存在；要么去重，要么把重复样本标记为契约外。

本章练习

本章回顾

1. 数组中数值和下标相等的元素就是numbers[i]等于i的不动点。
2. 单调递增数组还必须由唯一整数构成，才能保证相邻值至少增加1。
3. 差值序列numbers[i]减i非递减，但不一定严格递增，所以可能有多个解。
4. 比较numbers[mid]与mid：值小则向右，值大则向左，相等立即返回。
5. 严格递增证明使每轮可以二分排除一半区间，总时间O(log n)。
6. 作者返回任意解；第2组有两个解，但当前中点路径返回0。
7. 重复、乱序和错误length都在契约外，源码不会完整验证。
8. 7组测试覆盖答案位置、跨零无解、单元素和空指针。

名词解释