面试题53（一）：数字在排序数组中出现的次数

从“找到一个3还不够”开始

先预测：在1、2、3、3、3、3、4、5中，普通二分第一次可能命中下标3，但答案不是1。题目问数字在排序数组中出现的次数，必须知道整段3从哪里开始、在哪里结束。

非递减排序保证相同值不会分散在多个位置：所有k构成一个连续段。若该段首下标first为2、尾下标last为5，出现次数就是5减2加1等于4。

线性扫描当然能数出4，但没有利用排序信息。作者把问题改写成两个边界查找：二分查找第一个k，再二分查找最后一个k。

第一个k的判定条件

普通二分命中data[middle]等于k时不能立刻返回。只有middle等于0，或左邻data[middle减1]不等于k，middle才是。

若左邻仍等于k，真正的第一个k一定在左半区间，因此把end改为middle减1继续二分。若中间值大于k也向左；若小于k则向右。

示例第一次在下标3命中3，但下标2仍是3，所以搜索0到2；下标1值2小于3，转到2到2；下标2命中且左邻为2，返回first等于2。

最后一个k是镜像搜索

最后一个k称为。命中时只有middle等于length减1，或右邻不等于k，才能返回。

若右邻仍等于k，真正尾边界在右半，令start等于middle加1。中间值小于k也向右，大于k则向左。

示例先在下标3命中但右邻仍为3，于是搜索4到7；下标5命中且右邻下标6为4，返回last等于5。

忠实还原作者两次递归

作者入口仅在data非空且length大于0时执行搜索。两个辅助函数都以start大于end为失败基例并返回-1。

int GetFirstK(
    const int* data,
    int length,
    int k,
    int start,
    int end) {
    if (start > end) {
        return -1;
    }
 
    const int middleIndex =
        (start + end) / 2;
    const int middleData =
        data[middleIndex];
 
    if (middleData == k) {
        if ((middleIndex > 0 &&
             data[middleIndex - 1] != k) ||
            middleIndex == 0) {
            return middleIndex;
        }
        end = middleIndex - 1;
    } else if (middleData > k) {
        end = middleIndex - 1;
    } else {
        start = middleIndex + 1;
    }
    return GetFirstK(
        data, length, k, start, end);
}
 
int GetLastK(
    const int* data,
    int length,
    int k,
    int start,
    int end) {
    if (start > end) {
        return -1;
    }
 
    const int middleIndex =
        (start + end) / 2;
    const int middleData =
        data[middleIndex];
 
    if (middleData == k) {
        if ((middleIndex < length - 1 &&
             data[middleIndex + 1] != k) ||
            middleIndex == length - 1) {
            return middleIndex;
        }
        start = middleIndex + 1;
    } else if (middleData < k) {
        start = middleIndex + 1;
    } else {
        end = middleIndex - 1;
    }
    return GetLastK(
        data, length, k, start, end);
}

GetFirstK的length参数在函数体中没有使用；GetLastK需要它判断middle是否为末下标。保留参数有助于对齐作者签名，现代封装可用span统一边界。

入口如何组合两个边界

int GetNumberOfK(
    const int* data,
    int length,
    int k) {
    int number = 0;
    if (data != nullptr && length > 0) {
        const int first = GetFirstK(
            data, length, k, 0, length - 1);
        const int last = GetLastK(
            data, length, k, 0, length - 1);
 
        if (first > -1 && last > -1) {
            number = last - first + 1;
        }
    }
    return number;
}

last减first加1是。漏掉加1会让单元素命中返回0，也会把四个3算成3。

作者无论first是否找到都会执行GetLastK。若first为-1，可以直接返回0并省掉第二次搜索；这只是常数优化，不改变O(logn)复杂度。

正确性：为何向一侧收缩不会丢边界

以左边界为例。若middle值小于k，排序保证middle及其左边都不可能等于k，舍弃左半安全；若middle值大于k，右半也不可能包含第一个k，向左安全。

若middle等于k但左邻也等于k，middle确定不是第一个，而真正左边界必在start到middle减1中。若左邻不同或middle为0，排序保证更左侧都严格小于k，当前就是左边界。

右边界证明完全镜像。两个搜索都维护“若目标边界存在，它仍在当前闭区间内”的不变式；每次至少排除一半，最终找到边界或得到start大于end。

这类修改过命中分支、专门寻找最左或最右满足位置的搜索称为。

半开区间与单调谓词视角

作者通过检查相邻元素确认边界；另一种更通用的理解是寻找单调布尔序列第一次变真。对左边界，谓词是“当前值大于或等于k”：排序数组上的结果先连续为假，随后连续为真，第一次真就是lower_bound。若该位置越过数组末尾或值不等于k，目标不存在。

对右边界之外的位置，谓词是“当前值严格大于k”：它同样从假变真，第一次真就是upper_bound。目标次数等于upper_bound位置减lower_bound位置。这样定义使用半开区间左闭右开，搜索区间初始为0到length；循环保持答案一定在lo到hi中，取mid后若谓词为真就令hi等于mid，否则令lo等于mid加1，直到lo等于hi。

这个模板不读取middle左右邻居，因此空数组和数组端点都由半开区间自然覆盖，也能避免middle加1越界。作者版本与模板结果完全一致：GetFirstK返回lower_bound命中的下标，GetLastK返回upper_bound前一位。理解单调谓词后，可把同一方法迁移到“第一个满足容量的时间”“最后一个不超过预算的值”等问题，而不是死记两份镜像递归。

如果同一个排序数组要回答很多目标值查询，每次两次二分的成本是O(logn)，q次为O(q logn)，额外空间常数。也可以预先构造值到频次的哈希表，以O(n)时间和O(u)空间换取每次平均O(1)查询，其中u是不同值数量。是否预处理取决于查询批量、内存预算和数组是否会更新；单次查询时无需建立整张表。

排序前提不可隐含

排序若由函数内部完成，会把整体复杂度变为O(n log n)，只查询一次时通常不如O(n)计数；已有排序或需要多次查询时，二分优势才成立。

对于降序数组，比较方向要全部反转。只改一个分支会造成搜索区间朝错误方向移动。

中点与下标类型

源码用start加end再除2。两者都接近int上限时加法可能溢出，即使最终中点本可表示。稳健写法是start加end减start的一半。

#include <algorithm>
#include <span>
 
std::size_t numberOfK(
    std::span<const int> values,
    int k) {
    const auto range =
        std::equal_range(
            values.begin(), values.end(), k);
    return static_cast<std::size_t>(
        range.second - range.first);
}

标准库equal_range返回第一个不小于k的位置与第一个大于k的位置，是半开区间；二者距离直接是次数，不再加1。它同样要求输入按相同比较器排序。

手写现代版可用size_t半开区间避免负下标；失败时返回length作为边界哨兵，或使用optional。不要把-1直接转为size_t，否则会变成巨大正数。

空输入与目标不存在

data为nullptr或length小于等于0时入口返回0，不调用辅助函数。非空零长度也安全，因为length大于0条件不成立。

目标不存在时两个递归最终都返回-1；入口只有在两者均非负时才做差，因此返回0。目标小于最小值会持续向左，大于最大值会持续向右，都自然进入空区间。

返回次数不会超过length，因此在作者int长度契约内差值可表示。若容器长度使用size_t，返回类型也应使用size_t。

与错误旧页的语义分界

旧页标题和正文讲“出现频率超过n除k的数字”，使用广义Boyer-Moore候选抵消。那是另一道高频元素问题：

• 它不要求数组排序。
• 参数k是频率阈值分母。
• 返回可能有多个候选值。
• 需要最终频次验证。

本题中的k只是要查询的具体数值，输入必须排序，返回一个出现次数。两题仅变量名偶然相同，算法目标完全不同；本次重构已删除所有候选池与抵消语义。

作者11组测试逐项还原

1. 重复段在中间，1、2、3、3、3、3、4、5中查3，期望4。
2. 重复段在开头，3、3、3、3、4、5中查3，期望4。
3. 重复段在结尾，1、2、3、3、3、3中查3，期望4。
4. 目标2缺在数组内部，期望0。
5. 目标0小于最小值1，期望0。
6. 目标6大于最大值5，期望0。
7. 数组全是3且查3，期望4。
8. 数组全是3但查4，期望0。
9. 单元素3且查3，期望1。
10. 单元素3但查4，期望0。
11. nullptr、长度0、查0，期望0。

这11组覆盖重复段三种位置、三类缺失、全同数组、单元素和空指针。未覆盖非空零长度、降序或无序输入，因为它们分别是等价空表示或契约外输入。

#include <cassert>
 
void testNumberOfK() {
    const int data[] =
        {1, 2, 3, 3, 3, 3, 4, 5};
    assert(GetNumberOfK(data, 8, 3) == 4);
    assert(GetNumberOfK(data, 8, 2) == 1);
    assert(GetNumberOfK(data, 8, 0) == 0);
    assert(GetNumberOfK(data, 8, 6) == 0);
 
    const int all[] = {3, 3, 3, 3};
    assert(GetNumberOfK(all, 4, 3) == 4);
    assert(GetNumberOfK(all, 4, 4) == 0);
 
    int sentinel = 0;
    assert(GetNumberOfK(&sentinel, 0, 0) == 0);
    assert(GetNumberOfK(nullptr, 0, 0) == 0);
}

随机有序数组可用线性std::count作为参考，与边界二分对拍。生成数据后必须排序，再随机选择存在值、区间间隙和范围外目标，才能覆盖三类搜索方向。

本章练习

本章回顾

1. 数字在排序数组中出现的次数等于目标连续段的长度。
2. 普通二分命中任意k不够，必须二分查找第一个k。
3. 左边界命中条件是下标0或左邻不等于k。
4. 二分查找最后一个k使用下标末端或右邻不同的镜像条件。
5. 两边界存在时次数为last减first加1；不存在时返回0。
6. 两次搜索总复杂度O(logn)，不会因重复段很长退化。
7. 算法要求非递减排序；旧页的广义投票属于另一道题。
8. 作者11组测试覆盖中间、两端、缺失、全同、单元素与空指针。

名词解释