思路。左闭右闭版以「存在则在 \([lo, hi]\)」为不变量；左闭右开版以「\([0, lo)\) 全小于 target、\([hi, n)\) 全大于 target」为不变量。

int binarySearch(vector<int>& a, int target) {   // 左闭右闭 [lo, hi]
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {                    // 区间非空才继续
        int mid = lo + (hi - lo) / 2;    // 防溢出的中点写法
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;  // mid 已排除，答案在右侧
        else                 hi = mid - 1;  // mid 已排除，答案在左侧
    }
    return -1;                            // 区间为空，不存在
}

int binarySearchHO(vector<int>& a, int target) { // 左闭右开 [lo, hi)
    int lo = 0, hi = (int)a.size();
    while (lo < hi) {                     // 半开区间非空
        int mid = lo + (hi - lo) / 2;     // mid 恒 < hi，下取整安全
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else                 hi = mid;    // mid 可能是答案，不能减一
    }
    return -1;
}

死循环演示。若在「找最后一个满足条件的位置」这类问题里随手写：

while (lo < hi) {
    int mid = (lo + hi) / 2;      // 下取整
    if (a[mid] <= x) lo = mid;    // 错误：区间只剩 2 个元素时 mid == lo
    else hi = mid - 1;
}

取 \(lo = 2\)、\(hi = 3\)：mid 恒为 2，若判断走进 \(lo = mid\)，区间永远是 \([2, 3)\)——程序挂死。修正：收缩侧为 lo 时中点必须上取整，写 \(mid = lo + (hi - lo + 1) / 2\)。

复杂度与边界。时间 \(O(\log n)\)，空间 \(O(1)\)。边界：空数组（两个版本都直接返回 −1）、单元素、target 小于全部或大于全部（区间缩空自然退出）、有重复时本写法返回「某个」匹配位置——要精确到第一个需换 lower_bound 语义（见例题 2）。

面试怎么讲。写之前先声明约定：「我采用左闭右闭，不变量是答案若存在必在闭区间内」；写完用长度 2 的区间口头验证一轮终止性。这个习惯本身就是考点。

建模。整体无序，但任意取 mid 后，\(a[lo] \le a[mid]\) 与 \(a[mid] \le a[hi]\) 二者必有一个成立，即至少一半是有序的。先识别有序的一半，再在有序范围内做两次比较精确判断 target 是否在其中：在则收缩到这半，不在则收缩到另一半。不变量「target 若存在必在 \([lo, hi]\)」全程保持，每轮区间减半。

int searchRotated(vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[lo] <= a[mid]) {            // 左半 [lo, mid] 有序（无重复时）
            if (a[lo] <= target && target < a[mid])
                hi = mid - 1;             // target 落在有序的左半
            else
                lo = mid + 1;             // 否则必在右半
        } else {                          // 右半 [mid, hi] 有序
            if (a[mid] < target && target <= a[hi])
                lo = mid + 1;             // target 落在有序的右半
            else
                hi = mid - 1;
        }
    }
    return -1;
}

数值走查。a = [4, 5, 6, 7, 0, 1, 2]，target = 0：第一轮 \(lo=0, hi=6, mid=3\)，\(a[0]=4 \le a[3]=7\) 判左半有序；0 不在 \([4, 7)\) 内，\(lo = 4\)。第二轮 \(lo=4, hi=6, mid=5\)，\(a[4]=0 \le a[5]=1\) 左半有序；\(a[4] \le 0 \lt a[5]\) 成立，\(hi = 4\)。第三轮 \(mid = 4\)，\(a[4] = 0\) 命中，返回 4。三轮 \(\log_2 7 \approx 2.8\)，符合预期。

复杂度与边界。时间 \(O(\log n)\)，空间 \(O(1)\)。边界：未旋转的数组（永远走「左半有序」分支，退化为普通二分，仍正确）；单元素；两元素（mid = lo，「左半有序」判断自身成立，逻辑不变）；target 不存在时区间缩空返回 −1。有重复元素的变式（旋转数组 II）：当 \(a[lo] = a[mid] = a[hi]\) 时无法判断哪半有序，必须 lo、hi 各收缩一步，最坏 \(O(n)\)——面试要主动说出来。

面试怎么讲。先讲不变量再讲分支：「切一半必有一半有序，有序的一半可以精确判断 target 是否在内，所以每轮仍能安全扔一半」。追问「为什么不能直接比较 a[mid] 与 target」时回答：整体无序，该比较无法定位 target 在哪一侧，必须借有序半边做桥。

建模。条件「\(a[i] \ge x\)」随下标单调：前段全为假、后段全为真。要找真假分界，用左闭右开不变量：\(a[0, lo)\) 全小于 x，\(a[hi, n)\) 全不小于 x。

int lowerBound(vector<int>& a, int x) {   // 第一个 >= x 的下标
    int lo = 0, hi = (int)a.size();
    while (lo < hi) {                      // 不变量：[0,lo) < x，[hi,n) >= x
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < x) lo = mid + 1;      // mid 确认 < x，可安全排除
        else             hi = mid;         // mid 满足 >= x，可能是答案
    }
    return lo;                             // lo == hi，两段断言在此相接
}

正确性论证。初始 \(lo = 0\)、\(hi = n\)，两个空区间让断言平凡成立。每轮收缩后断言保持：进入 \(lo = mid + 1\) 的前提是 \(a[mid] \lt x\)，因此 \([0, mid+1)\) 全小于 x；进入 \(hi = mid\) 的前提是 \(a[mid] \ge x\)，因此 \([mid, n)\) 全不小于 x。循环结束时 \(lo = hi\)，左侧断言给出「\(lo\) 前面都小于 x」，右侧断言给出「\(lo\) 起都 \(\ge x\)」，\(lo\) 恰为分界。终止性：\(mid \lt hi\) 严格成立（下取整且 \(lo \lt hi\)），两种收缩都严格减小区间。

复杂度与边界。\(O(\log n)\)、\(O(1)\)。边界：x 小于全部元素返回 0；大于全部返回 n（调用方须检查 n 越界语义）；重复元素正是它的主场——「第一个」位置被精确锁定，普通二分做不到。改成 upper_bound（第一个 \(\gt x\)）只需把判定换成 \(a[mid] \le x\)。

面试怎么讲。强调「这类题的正确打开方式是写不变量而不是试边界」，然后给应用：插入位置、计数某值出现次数 = upper_bound − lower_bound、二分答案的判定函数都长这样。

方法一：排序。基准解，一行核心逻辑，\(O(n \log n)\) 时间。面试先写它并声明「保证正确，下面优化」，同时钉住 k 的计数起点。

int kthBySort(vector<int> a, int k) {        // k 从 1 计
    sort(a.begin(), a.end());
    return a[k - 1];
}

方法二：QuickSelect。复用 007 章的 Lomuto partition（含随机化）。每轮只递归/迭代包含第 k 位的一侧，平均 \(O(n)\)、最坏 \(O(n^2)\)、迭代版 \(O(1)\) 额外空间。

int partition(vector<int>& a, int lo, int hi) {  // 随机化 Lomuto
    int r = lo + rand() % (hi - lo + 1);
    swap(a[r], a[hi]);
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; ++j)
        if (a[j] <= pivot) swap(a[i++], a[j]);
    swap(a[i], a[hi]);
    return i;                              // 基准的最终下标
}

int quickSelect(vector<int>& a, int k) {   // k 从 0 计：第 k 小 = 下标 k
    int lo = 0, hi = (int)a.size() - 1;
    while (true) {
        if (lo == hi) return a[lo];
        int p = partition(a, lo, hi);
        if (p == k) return a[p];           // 基准恰好在第 k 位
        if (p < k) lo = p + 1;             // 第 k 小在右侧，扔掉左侧
        else       hi = p - 1;             // 在左侧，扔掉右侧
    }
}

方法三：BFPRT（中位数的中位数）。基准不再是随机元素，而是递归求出的「中位数的中位数」，保证两侧各占至少三成，最坏 \(O(n)\)。

int bfprt(vector<int>& a, int lo, int hi, int k);  // 前向声明

int medianOfMedians(vector<int>& a, int lo, int hi) {
    int n = hi - lo + 1;
    if (n <= 5) {                           // 递归基：小组直接排序取中位数
        sort(a.begin() + lo, a.begin() + hi + 1);
        return a[lo + n / 2];
    }
    vector<int> meds;
    for (int i = lo; i <= hi; i += 5) {
        int r = min(i + 4, hi);             // 每组至多 5 个，组内排序 O(1)
        sort(a.begin() + i, a.begin() + r + 1);
        meds.push_back(a[i + (r - i) / 2]); // 收集各组中位数
    }
    // 递归地对中位数组成的数组求中位数
    return bfprt(meds, 0, (int)meds.size() - 1, (int)meds.size() / 2);
}

int bfprt(vector<int>& a, int lo, int hi, int k) {  // k 为全局下标
    int pivot = medianOfMedians(a, lo, hi);
    int lt = lo, i = lo, gt = hi;           // 三路划分：< | == | >
    while (i <= gt) {
        if (a[i] < pivot)      swap(a[lt++], a[i++]);
        else if (a[i] > pivot) swap(a[i], a[gt--]);
        else                    ++i;
    }
    if (k < lt)      return bfprt(a, lo, lt - 1, k);  // 落在小于段
    else if (k > gt) return bfprt(a, gt + 1, hi, k);  // 落在大于段
    return pivot;                            // k 落在等于段，直接命中
}

为什么最坏线性（数值化）。约 \(n/5\) 组、一半组的中位数 \(\ge M\)，每组另有 2 个元素 \(\ge\) 本组中位数，故至少约 \(3n/10\) 个元素不小于 M；对称地至少约 \(3n/10\) 个不大于 M。递归的大侧至多 \(7n/10\)，加上求中位数的中位数的 \(n/5\)，\(\tfrac15 + \tfrac7{10} = \tfrac9{10} \lt 1\)，各层工作量几何衰减，总和 \(\le 10 \cdot c n\)，即 \(O(n)\)。

复杂度与边界（三法对照）。排序法 \(O(n \log n)\) 无退化；QuickSelect 平均 \(O(n)\)、最坏 \(O(n^2)\)（随机化使其概率上几乎不出现）；BFPRT 恒 \(O(n)\) 但常数大。共同边界：k 必须落在 1..n（先校验，防止越界）；全相等数组——三路版 QuickSelect 与 BFPRT 一次划分即返回，朴素两路 QuickSelect 退化为平方；负数不影响（只做比较）；三种方法都会重排输入，不允许修改时先复制（空间代价 \(O(n)\)）。中位数即 \(k = \lfloor n/2 \rfloor\) 的第 k 小，两个 k 的解平均后是偶数个元素的中位数。

面试怎么讲。按「排序 → QuickSelect → BFPRT」的顺序主动升级：先给基准解，再讲「只递归一侧所以平均线性」，最后补「最坏线性的办法是把随机基准换成中位数的中位数，代价是常数」。追问「为什么不直接用 nth_element」时答：它就是 introselect（QuickSelect + 恶化退化的组合），生产用它，但面试考的是原理。数据流上的第 k 大不该用本节方法（数据不能全读进内存），用大小为 k 的堆，见 004 章。