考研笔记

板子：二分查找

两个版本：找 x 在不在（找到就返回），找第一个 的位置（边界版，插入、计数、找区间都靠它）。

代码

int binSearch(int A[], int n, int x) {     // 升序表中找 x，返回下标；没有返回 -1
    int l = 0, r = n - 1;                  // 查找区间是闭区间 [l, r]
    while (l <= r) {                       // 区间里还有元素就继续；l > r 说明区间空了
        int mid = (l + r) / 2;
        if (A[mid] == x) return mid;
        if (A[mid] < x) l = mid + 1;       // mid 已经比较过，不再留在区间里
        else r = mid - 1;
    }
    return -1;
}
 
int lowerBound(int A[], int n, int x) {    // 第一个 >= x 的下标；全都小于 x 时返回 n
    int l = 0, r = n;                      // 答案一定在 [l, r] 内，r = n 表示「没有 >= x 的」
    while (l < r) {                        // l == r 时只剩一个位置，它就是答案
        int mid = (l + r) / 2;             // 向下取整，保证 mid < r，r = mid 一定会缩小区间
        if (A[mid] >= x) r = mid;          // mid 可能就是答案，保留
        else l = mid + 1;                  // mid 太小，一定不是答案
    }
    return l;
}

复杂度：时间 ，空间 。

变形

  • 第一个 的位置：把 >= 改成 >。
  • 出现了几次：「第一个 的位置」减「第一个 的位置」。
  • 找 ，找到就和后继交换，找不到就插入并保持有序（王道 2.2 综合题）：插入位置就是 lowerBound 的返回值。

易错点

  • 循环条件和收缩方式要配套：while (l <= r) 配 r = mid - 1，while (l < r) 配 r = mid。混着写会死循环或者漏掉答案。
  • 教材下标从 1 开始，mid = (low + high) / 2 向下取整。判定树、ASL 这类手算题按教材口径算，见 7.2.2 折半查找。
  • 竞赛里为了防溢出会写 l + (r - l) / 2，考研一般不考虑溢出。

链接

反向链接