はじめに

みなさんこんにちは、ALH開発事業部のREIYAです。
二分探索っていろいろありますが、個人的にこうまとまっていて欲しい！というのが無かったので作りました。

偉大なるけんちょん大先生のこちらの記事もどうぞ。

おことわり

この記事は二分探索の説明というより、こういう使い方をしますみたいな記事です。仕組みの詳しい説明が欲しい方には合わないかもしれませんのでご留意ください。

今回取り上げる項目です。

• 配列上のにぶたん

• 整数上のにぶたん

• 実数上のにぶたん

配列上

単調性のあるデータが配列上にある場合有効です。
0から99までの連番配列で、初めて30以上になるインデックスは？

...簡単ですね？インデックスと値が同じですから30です。

#include <iostream>
#include <numeric>
#include <vector>
#include <algorithm>
int main() {
    // 連番
    std::vector<int> arr(100);
    std::iota(arr.begin(), arr.end(), 0);
    // 二分探索し、イテレータを取得
    auto itr = lower_bound(arr.begin(), arr.end(), 30);
    std::cout << "val:" << *itr << std::endl;
    // インデックスを取得する場合こう
    int idx = lower_bound(arr.begin(), arr.end(), 30) - arr.begin();
    std::cout << "idx:" << idx << std::endl;
}

val:30
idx:30

import bisect
arr = list(range(100))
print(bisect.bisect_left(arr, 30)) # 30

A以下の個数

初めてAより大きい要素、より左側の個数です。
以下だと0から30の31個です。

#include <iostream>
#include <numeric>
#include <vector>
#include <algorithm>
int main() {
    // 連番
    std::vector<int> arr(100);
    std::iota(arr.begin(), arr.end(), 0);
    // 30より大きいものの個数
    int cnt = upper_bound(arr.begin(), arr.end(), 30) - arr.begin();
    std::cout << cnt << std::endl; // 31
}

import bisect
arr = list(range(100))
def ika_cnt(arr, x):
    i = bisect.bisect_right(arr, x)
    return i
print(ika_cnt(arr, 30)) # 31

Aより小さい個数

30を含み、30以上のものを全部抜けば
30より小さい要素「0~29」の30個です。

#include <iostream>
#include <numeric>
#include <vector>
#include <algorithm>
int main() {
    // 連番
    std::vector<int> arr(100);
    std::iota(arr.begin(), arr.end(), 0);
    // 30より大きいものの個数
    int cnt = lower_bound(arr.begin(), arr.end(), 30) - arr.begin();
    std::cout << cnt << std::endl; // 30
}

import bisect
arr = list(range(100))
def sita_cnt(arr, x):
    i = bisect.bisect_left(arr, x)
    return i
print(sita_cnt(arr, 30)) # 30

整数上

さて、配列上でなければできないのかというともちろんそんな訳なくて、有名な「年齢あてゲーム」は整数上のものですね。
整数全体は単調です。

年齢を質問の回数が少なく当てます。ただし0~99。
あなた「50以上ですか？」: NO→0~49とわかる
あなた「25以上ですか？」: YES→25~49とわかる
みたいなやつ。

#include <iostream>
int main() {
    // 30以上ですか？を聞く
    auto test = [&](long long x) -> bool { return x >= 30; };
    long long L = 0, R = 1, MID = 0;
    while (!test(R)) R <<= 1;
    // ここが二分探索です。
    while (abs(R - L) > 1) (test(MID = L + (R - L) / 2) ? R : L) = MID;
    std::cout << R << std::endl;
}

ポイントは
LがNG、RがOKなこと。
この幅を狭めることで、NGからOKに切り替わりタイミングを知るのが二分探索です。

while (!test(R)) R <<= 1;

ここで最初適当にR=1としていたので、条件OKになるまで2倍を繰り返しています。これを指数探索などと言います。
また、$${(L + R) / 2}$$でなく$${L + (R - L) / 2}$$としているのは桁溢れ対策です。

pythonは略

実数上

実数です。簡単に言えば小数OKになりますので話変わってきます。
まず整数上での探索の時は終了条件に

while (abs(R - L) > 1)

としていましたが、これだと例えばL=29、R=30の場合に終了します。求めたいのは実数なので、29.5が欲しい場合これではダメですね。

こうします。

#include <iostream>
#include <iomanip>
#include <cmath>
constexpr long double EPS = 1e-14;
int main() {
    // doubleは桁数52bit程度の精度ですのでご注意
    auto test = [&](double x) -> bool { return x >= 31.4; };
    double L = 0, R = 1, MID = 0;
    while (!test(R)) R *= 2; // 指数探索
    // 絶対誤差と相対誤差で評価
    auto ABS = [&]() { return abs(R - L) > EPS; };
    auto REL = [&]() { return abs(R - L) / std::max(R, L) > EPS; };
    while (ABS() and REL()) (test(MID = L + (R - L) / 2) ? R : L) = MID;
    std::cout << std::fixed << std::setprecision(20);
    std::cout << R << std::endl; // 31.50000000000000000000
}

余談

$${2^{16}}$$を求めるには1に2を16回かけるよりも、2を2乗するを4回すれば良いですね？

#include <iostream>
int main() {
    int N = 1;
    for (int i = 0; i < 16; ++i) N *= 2;
    std::cout << N << std::endl; // 65536

    N = 2;
    for (int i = 0; i < 4; ++i) N *= N;
    std::cout << N << std::endl; // 65536
}

二分探索じゃなくて二分累乗とかって呼ばれますが（厳密には違いますが）、こういった工夫は歴史上最もすごいと名高いアルゴリズムFFTなどにも使われています。

やはり二分探索こそ賢い工夫のベースなのだと私は思っています。

さいごに

にぶたん、たのしい。

ALHについて知る

↓ ↓ ↓　採用サイトはこちら　↓ ↓ ↓

↓ ↓ ↓　コーポレートサイトはこちら　↓ ↓ ↓

↓ ↓ ↓　もっとALHについて知りたい？　↓ ↓ ↓