一、整數(shù)二分

二分查找分為整數(shù)二分和浮點(diǎn)數(shù)二分，一般所說的二分查找都是指整數(shù)二分。

1.1 二分查找模板

滿足單調(diào)性的數(shù)組一定可以使用二分查找，但可以使用二分查找的數(shù)組不一定需要滿足單調(diào)性。

不妨假設(shè)我們找到了條件 $C_1$，它和它的對(duì)立條件 $C_2$ 能夠?qū)?shù)組 $a$ 一分為二，如下圖所示：

因?yàn)?$C_1$ 和 $C_2$ 互為對(duì)立，故總有 $C_1\cup C_2\equiv \text{True},C_1\cap C_2\equiv \text{False}$（用C++語言描述，就是 c1 || !c1 總是為真，c1 && !c1 總是為假）。換句話說，$?x\in a$，$x$ 至少滿足 $C_1$ 和 $C_2$ 中的一個(gè)，且 $x$ 不會(huì)同時(shí)滿足 $C_1$ 和 $C_2$。

觀察上圖可以發(fā)現(xiàn)，索引 $3$ 和索引 $4$ 這兩個(gè)位置都可以作為 $C_1$ 和 $C_2$ 的分界點(diǎn)。其中，索引 $3$ 是紅色區(qū)域的右邊界，索引 $4$ 是綠色區(qū)域的左邊界。而我們接下來要討論的二分查找模板就是用來尋找 $C_1$ 和 $C_2$ 的分界點(diǎn)的。

1.1.1 尋找右邊界的二分查找

前面說過，$C_1$ 和 $C_2$ 的分界點(diǎn)一共有兩個(gè)，因此我們的整數(shù)二分查找模板也有兩個(gè)。一個(gè)用來查找右邊界（即左側(cè)的分界點(diǎn)，對(duì)應(yīng)索引 $3$），一個(gè)用來查找左邊界（即右側(cè)的分界點(diǎn)，對(duì)應(yīng)索引 $4$）。這里首先介紹查找右邊界的模板。

因?yàn)椴檎业氖?strong>紅色區(qū)域的右邊界，所以先定義一個(gè)函數(shù) check(i)，其中參數(shù) $i$ 是索引。當(dāng) $i$ 位于紅色區(qū)域，即 $0\le i\le 3$ 時(shí)，check(i) 為真；當(dāng) $i$ 位于綠色區(qū)域，即 $4\le i\le 7$ 時(shí)，check(i) 為假。

初始時(shí)設(shè)置左右兩個(gè)指針分別位于數(shù)組的左右兩端，每次循環(huán)時(shí)計(jì)算 $mid=\frac{l+r}{2}$（至于 $mid$ 到底取多少稍后會(huì)說），然后判斷 check(mid) 的值（為實(shí)現(xiàn)二分查找，我們需要確保每次縮小區(qū)間時(shí)答案都落在區(qū)間內(nèi)。這樣一來，當(dāng)最終 l == r 時(shí)，l 就是我們需要的答案）。如果 check(mid) 為真，說明 $mid$ 位于紅色區(qū)域，且 $mid$ 有可能就是右邊界，因此接下來令 $l=mid$ 來縮小查找范圍（因?yàn)槲覀円ＷC縮小后的區(qū)間仍然包含答案）；如果 check(mid) 為假，說明 $mid$ 位于綠色區(qū)域，且 $mid$ 必不可能是紅色區(qū)域的右邊界，因?yàn)?$mid$ 最多是索引 $4$，因此令 $r=mid?1$ 來縮小查找范圍。

接下來重點(diǎn)關(guān)注 $mid$ 到底該取多少。如果 $mid=\frac{l+r}{2}$，其中的除法代表整除，在某一輪循環(huán)出現(xiàn)了 $r?l=1$，則 $mid=\frac{2l+1}{2}=l$。若 check(mid) 為真，則更新后的區(qū)間仍然為 $[l,r]$，這就會(huì)導(dǎo)致無限循環(huán)。事實(shí)上，只需要取 $mid=\frac{l+r+1}{2}$，若 check(mid) 為真，則 $mid=r$，更新后的區(qū)間為 $[r,r]$，循環(huán)結(jié)束。若 check(mid) 為假，則更新后的區(qū)間為 $[l,l]$，循環(huán)結(jié)束。

尋找右邊界的二分查找模板：

int right_bound(int l, int r) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

1.1.2 尋找左邊界的二分查找

類似1.1.1節(jié)中的分析，因?yàn)椴檎业氖?strong>綠色區(qū)域的左邊界，所以先定義一個(gè)函數(shù) check(i)，其中參數(shù) $i$ 是索引。當(dāng) $i$ 位于綠色區(qū)域，即 $4\le i\le 7$ 時(shí)，check(i) 為真；當(dāng) $i$ 位于紅色區(qū)域，即 $0\le i\le 3$ 時(shí)，check(i) 為假。

初始時(shí)設(shè)置左右兩個(gè)指針分別位于數(shù)組的左右兩端，每次循環(huán)時(shí)計(jì)算 $mid=\frac{l+r}{2}$（至于 $mid$ 到底取多少稍后會(huì)說），然后判斷 check(mid) 的值。如果 check(mid) 為真，說明 $mid$ 位于綠色區(qū)域，且 $mid$ 有可能就是左邊界，因此接下來令 $r=mid$ 來縮小查找范圍；如果 check(mid) 為假，說明 $mid$ 位于紅色區(qū)域，且 $mid$ 必不可能是綠色區(qū)域的左邊界，因?yàn)?$mid$ 最多是索引 $3$，因此令 $l=mid+1$ 來縮小查找范圍。

接下來重點(diǎn)關(guān)注 $mid$ 到底該取多少。如果 $mid=\frac{l+r}{2}$，其中的除法代表整除，在某一輪循環(huán)出現(xiàn)了 $r?l=1$，則 $mid=\frac{2l+1}{2}=l$。若 check(mid) 為真，則更新后的區(qū)間為 $[l,l]$，循環(huán)結(jié)束。若 check(mid) 為假，則更新后的區(qū)間為 $[r,r]$，循環(huán)結(jié)束。綜上所述，$mid$ 取 $\frac{l+r}{2}$ 即可。

尋找左邊界的二分查找模板：

int left_bound(int l, int r) {
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

1.2 應(yīng)用：尋找元素的起始位置和終止位置

原題鏈接：AcWing 789. 數(shù)的范圍

以 a = [1, 3, 3, 3, 4] 為例，數(shù)字 $3$ 的起始位置和終止位置分別是 $1$ 和 $3$（索引）。如何利用1.1節(jié)中的模板來完成此題呢？

現(xiàn)對(duì)數(shù)組 $a$ 作出劃分，若令 $C_1:a[i]<x,C_2:a[i]\ge x$（注意必須保證 $C_1,C_2$ 互為對(duì)立），則求 $x$ 的起始位置便轉(zhuǎn)化成了求 $C_2$ 區(qū)域的左邊界。若令 $C_1:a[i]\le x,C_2:a[i]>x$，則求 $x$ 的終止位置便轉(zhuǎn)化成了求 $C_1$ 區(qū)域的右邊界。

在求 $C_2$ 區(qū)域的左邊界時(shí)，check(mid) 即為 a[mid] >= x。在求 $C_1$ 區(qū)域的右邊界時(shí)，check(mid) 即為 a[mid] <= x。

AC代碼如下：

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N];

int left_bound(int l, int r, int x) {
    while (l < r) {
        int mid = l + r >> 1;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

int right_bound(int l, int r, int x) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (a[mid] <= x) l = mid;
        else r = mid - 1;
    }
    return l;
}

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) cin >> a[i];

    while (q--) {
        int k;
        cin >> k;
        int begin = left_bound(0, n - 1, k);
        if (a[begin] != k) cout << "-1 -1" << endl;
        else cout << begin << " " << right_bound(0, n - 1, k) << endl;
    }

    return 0;
}

二、浮點(diǎn)數(shù)二分

2.1 浮點(diǎn)數(shù)二分模板

相比整數(shù)二分，浮點(diǎn)數(shù)二分就要簡單許多了，因?yàn)楦↑c(diǎn)數(shù)二分不涉及到邊界問題。

浮點(diǎn)數(shù)二分通常用來求某個(gè)數(shù) $x$ 的近似值（$x$ 不易直接求得，例如 $x=\sqrt{2}$ 等）。由于此時(shí)左右兩個(gè)指針也均為浮點(diǎn)數(shù)，所以我們不能直接判斷 l == r，而是判斷 r - l 是否小于預(yù)先設(shè)定的精度。

模板如下：

double fbsearch(double l, double r, double eps) {
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

一些注意事項(xiàng)：

• 若要求精確到小數(shù)點(diǎn)后 $k$ 位，則 $eps$ 取 $10^{?(k+2)}$;
• 若 $mid\ge x$，則 check(mid) 為真，否則為假。

2.2 應(yīng)用：數(shù)的三次方根

原題鏈接：AcWing 790. 數(shù)的三次方根

注意到當(dāng) $|x|<1$ 時(shí)，有 $|x^{1/3}|>|x|$，故選取 $l,r$ 時(shí)一定要謹(jǐn)慎。

因?yàn)?$10000^{1/3}<22$，所以這里取 $l=?22,r=22$ 即可。

#include <iostream>

using namespace std;

double x;

double fbsearch(double l, double r, double eps) {
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (mid * mid * mid >= x) r = mid;
        else l = mid;
    }
    return l;
}

int main() {
    cin >> x;
    printf("%lf", fbsearch(-22, 22, 1e-8));
    return 0;
}

三、使用STL進(jìn)行二分查找

3.1 std::binary_search

template< class ForwardIt, class T >
bool binary_search( ForwardIt first, ForwardIt last, const T& value );

該函數(shù)用來檢查 [first, last) 區(qū)間內(nèi)（該區(qū)間已排序）是否有數(shù)字等于 value，如果有返回 true，否則返回 false。

3.2 std::lower_bound

template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );

該函數(shù)用來返回 [first, last) 區(qū)間內(nèi)（該區(qū)間已排序）首個(gè)大于等于 value 的元素的迭代器，如果找不到這種元素則返回 last。

3.3 std::upper_bound

template< class ForwardIt, class T >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );

該函數(shù)用來返回 [first, last) 區(qū)間內(nèi)（該區(qū)間已排序）首個(gè)大于 value 的元素的迭代器，如果找不到這種元素則返回 last。

3.4 std::equal_range

template< class ForwardIt, class T >
std::pair<ForwardIt, ForwardIt>
    equal_range( ForwardIt first, ForwardIt last, const T& value );

該函數(shù)用來返回 [first, last) 區(qū)間內(nèi)（該區(qū)間已排序）所有等于 value 的元素的「范圍」。

「范圍」實(shí)際上是由兩個(gè)迭代器構(gòu)成的 pair。pair 中的第一個(gè)元素是 std::lower_bound 的返回值，pair 中的第二個(gè)元素是 std::upper_bound 的返回值。

接下來我們用STL來簡化1.2節(jié)中的代碼。

注意到對(duì)于數(shù)組而言，其迭代器就是指針，因此我們可以通過將返回的迭代器與數(shù)組名作差來得到迭代器所指向的元素的下標(biāo)。

簡化后的代碼如下：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int a[N];

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) cin >> a[i];

    while (q--) {
        int k;
        cin >> k;
        auto p = equal_range(a, a + n, k);
        if (*p.first != k) cout << "-1 -1" << endl;
        else cout << p.first - a << " " << p.second - a - 1 << endl;
    }

    return 0;
}

References

[1] https://www.acwing.com/activity/content/punch_the_clock/11/
[2] https://www.acwing.com/blog/content/31/
[3] https://zh.cppreference.com/w/cpp/algorithm/lower_bound文章來源地址http://www.zghlxwxcb.cn/news/detail-804568.html

到了這里，關(guān)于還不會(huì)二分查找？看這一篇就夠了的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！