二分查找

前置知识

排序，单调性，分治思想

目标

二分查找（背模板）

二分答案（理解check函数）

STL 用法

What

二分查找算法（binary search algorithm）

是一种在有序数组中查找某一特定元素的搜索算法。

使用二分的前提条件是，必须在单调有序的数组上进行，或者可以局部舍弃

每一次比较，都使搜索范围缩小一半。

最坏情况下，需要进行O(logn)次比较。

最直接的例子是，猜数字游戏。猜小了，往大里猜；猜大了，往小里猜。

整数二分

模板01

// 有序数组，找数字 k 第一次出现的位置(保证有答案)
int l = 0, r = n - 1, best = -1;
while (l <= r){
    int mid = (l + r) >> 1;
    if (a[mid] >= k) r = mid - 1, best = mid;
    else l = mid + 1;
}
cout << best;

// 有序数组，找数字 k 最后一次出现的位置(保证有答案)
int l = 0, r = n - 1, best = -1;
while (l <= r){
    int mid = (l + r) >> 1;
    if (a[mid] <= k) l = mid + 1, best = mid;
    else r = mid - 1;
}
cout << best;

模板02

// 有序数组，找数字 k 第一次出现的位置(保证有答案)
int l = 0, r = n - 1;
while (l < r){
    int mid = (l + r) >> 1;
    if (a[mid] >= k) r = mid;
    else l = mid + 1;
}
cout << l;

// 有序数组，找数字 k 最后一次出现的位置(保证有答案)
int l = 0, r = n - 1, best = -1;
while (l < r){
    int mid = (l + r + 1) >> 1;
    if (a[mid] <= k) l = mid;
    else r = mid - 1;
}
cout << l;

P2249 【深基13.例1】查找

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e6 + 10;

int a[N];
int n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    while (m--) {
        int x;
        scanf("%d", &x);

        int l = 1, r = n, best = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (a[mid] >= x) r = mid - 1, best = mid;
            else l = mid + 1;
        }

        if (best == -1 || a[best] != x) cout << -1 << ' ';
        else cout << best << ' ';
    }

    return 0;
}

STL

一般的数值查找，我们可以直接使用 STL

但如果是二分答案，我们则必须手写 check 函数

// 常见的场景，找大于x的第一个数，找小于x的最后一个数
// lower_bound() ，在指定区域内查找 大于等于 目标值的第一个元素
// upper_bound() ，在指定区域内查找 严格大于 目标值的第一个元素

// a是一个一维数组时，这时的pos对应的是下标
int pos = lower_bound(a, a + n, x) - a;
int pos = upper_bound(a, a + n, x) - a;

// a是一个vector时，返回迭代器。先检查是否等于 end()，再解引用
auto it = lower_bound(a.begin(), a.end(), x);
if (it != a.end()) cout << *it;

auto jt = upper_bound(a.begin(), a.end(), x);
if (jt != a.end()) cout << *jt;

浮点数二分

前面讲的二分，是整数值域上的二分。

如果遇到小数的问题，我们要使用下面的模板。

模板03

int T = 100;
while (T--) {
    double mid = (l + r) / 2;
    if (check(mid)) r = mid;
    else l = mid;
}
return l;

给定一个浮点数n，求它的三次方根

#include <iostream>

using namespace std;

int main() {
    double x;
    cin >> x;

    bool fushu = false;
    if (x < 0) fushu = true, x = -x;

    int T = 100;
    double l = 0, r = max(1.0, x);
    while (T--) {
        double mid = (l + r) / 2;
        if (mid * mid * mid >= x) r = mid;
        else l = mid;
    }

    cout << (fushu ? -l : l);

    return 0;
}

P2249 【深基13.例1】查找

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int a[N];
int n, m;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    while (m--) {
        int x;
        scanf("%d", &x);

        int pos = lower_bound(a, a + n, x) - a;
        if (a[pos] != x) printf("-1 ");
        else printf("%d ", pos + 1);
    }

    return 0;
}