LoginSignup
719
562

More than 5 years have passed since last update.

@drken(けんちょん (Otsuki))in株式会社NTTデータ数理システム

二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜

Last updated at Posted at 2018-04-20

0. はじめに

二分探索法は単純ながらも効果が大きく印象に残りやすいもので、アルゴリズム学習のスタート地点に彩られた花という感じです。二分探索というと「ソート済み配列の中から目的のものを高速に探索する」アルゴリズムを思い浮かべる方が多いと思います。巨大なサイズのデータを扱う場面の多い現代ではそれだけでも十分実用的ですが、二分探索法はもっとずっと広い適用範囲を持っています。

本記事では、二分探索法のエッセンスを抽象化して、適用範囲の広い「二分探索法の一般形」を紹介します。同時に無数にある二分探索の実装方法の中でも「めぐる式二分探索」がバグりにくいと感じているので、紹介したいと思います。
　

注意 1: 二分探索の計算時間について

二分探索の計算時間について簡単に触れておきたいと思います。例えば「$n$ 個の要素からなるソート済み配列から目的の値を探索する」というよく知られた設定であれば、

  • 単純な線形探索では $O(n)$ の時間がかかる
  • 二分探索を行えば $O(\log{n})$ の時間で済む

といった具合に、線形探索に比べて劇的に高速化することができます。ソート済み配列に関する探索の問題に限らず、他の問題設定に対しても「逐次的にやると $O(n)$ 回調べる必要があることを $O(\log{n})$ 回調べれば十分」という高速化を実現できることが多いです。

注意 2: 連続量に対する二分探索

本記事では離散量に対する二分探索のみを対象にしていますが、二分探索は連続的な問題に対しても有効です。それについては別途記事にしたいと思います。

1. 普通の二分探索から std::lower_bound() へ

二分探索は通常は「ソート済み配列の中から目的のものを探す」アルゴリズムを指します。そのような処理を実現する方法として、以下のような実装をよく目にします。仕様としては

  • 配列 a の中に値 key があれば、その index を返す (複数ある場合はどれか 1 つを返す)
  • 配列 a の中に値 key がなければ、-1 を返す

というものになっています。

#include <iostream>
#include <vector>
using namespace std;

vector<int> a = {1, 14, 32, 51, 51, 51, 243, 419, 750, 910};

// 目的の値 key の index を返すようにする (ない場合は -1)
int binary_search(int key) {
    int left = 0, right = (int)a.size() - 1; // 配列 a の左端と右端
    while (right >= left) {
        int mid = left + (right - left) / 2; // 区間の真ん中
        if (a[mid] == key) return mid;
        else if (a[mid] > key) right = mid - 1;
        else if (a[mid] < key) left = mid + 1;
    }
    return -1;
}

int main() {
    cout << binary_search(51) << endl; // a[4] = 51 (他に a[3], a[5] も)
    cout << binary_search(1) << endl; // a[0] = 1
    cout << binary_search(910) << endl; // a[9] = 910

    cout << binary_search(52) << endl; // -1
    cout << binary_search(0) << endl; // -1
    cout << binary_search(911) << endl; // -1
}

もう少し汎用的なものを考えてみましょう。例えば C++ の std::lower_bound() は

  • 配列 a の index (正確には iterator) のうち key 以上となる最小の index を返す

ようにしています。そうすれば単に「配列 a の中に key があるかどうかを探す」よりも

  • 配列 a の中に値 key がなくても、key が a の中で何番目に小さいかわかる
  • 配列 a の中に値 key が複数あったとき、そのうちの最小の index を取って来れる
  • 発展テクとして std::upper_bound() も併用すれば、配列 a の中に値 key をもつものが何個あるかもわかる

という風により多くの情報を得ることができます。次章でこの思想をさらに推し進めて、二分探索法を一般化します。

2. 一般化した二分探索法

std::lower_bound() がやりたいことは、結局は

  • a[index] >= key という条件を満たす最小の index を見つけたい

と言い表すことができます。

　

　

この std::lower_bound() をさらに一般化して、二分探索法は次のような場面で適用可能なアルゴリズムだということができます！

【やりたいこと】
x に関する「条件」がある。
以下のことがわかっているときに、条件を満たす最小の x を見つけたい

  • x = left は条件を満たさない
  • x = right は条件を満たす
  • left と right の間に条件を満たすようになる境目がある！
    • 境目まではずっと条件を満たしておらず、境目から先はずっと条件を満たしている (単調性)

これは以下に示すような非常に汎用的なコードで実現することができます。いわゆるめぐる式二分探索です。実装のお気持ちですが、

  • left は「常に」条件を満たさない
  • right は「常に」条件を満たす
  • right - left = 1 になるまで範囲を狭める (最後は right が条件を満たす最小)

という明快なロジックです。left と right の初期値の定め方だけ注意しておけば、何も考えなくとも書けるようになります。以下に lower_bound() の実装をしてみます:

#include <iostream>
#include <vector>
using namespace std;

vector<int> a = {1, 14, 32, 51, 51, 51, 243, 419, 750, 910};

// index が条件を満たすかどうか
bool isOK(int index, int key) {
    if (a[index] >= key) return true;
    else return false;
}

// 汎用的な二分探索のテンプレ
int binary_search(int key) {
    int left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    int right = (int)a.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

    /* どんな二分探索でもここの書き方を変えずにできる！ */
    while (right - left > 1) {
        int mid = left + (right - left) / 2;

        if (isOK(mid, key)) right = mid;
        else left = mid;
    }

    /* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
    return right;
}

int main() {
    cout << binary_search(51) << endl; // a[3] = 51 (さっきは 4 を返したが今回は「最小の index」なので 3)
    cout << binary_search(1) << endl; // a[0] = 1
    cout << binary_search(910) << endl; // a[9] = 910

    cout << binary_search(52) << endl; // 6
    cout << binary_search(0) << endl; // 0
    cout << binary_search(911) << endl; // 10 (場外)
}

二分探索をこのように一般化して考えることで、「ソート済配列の中での探索」に限らず様々な問題に活用することができます。注意点として、ここで挙げた一般化では

  • 求めたい境目を境にして「左側はすべて偽で、右側はすべて真」である

という単調性を仮定しましたが、「条件を満たす最小」を求めることにこだわらなければこの仮定はなくてもよく

  • 二分探索の初期値の一方が真、もう一方が偽になるようにしておいて、真偽の境目を 1 つ求める

という使い方もできます。単調性の仮定がなければ真偽の境目が複数あり得て、そのうちの 1 つが求まることになります。このような二分探索法フレームワークは、例えば方程式 f(x) = 0 の解をどれか 1 つ求めたい場面などで活用することができます。

3. めぐる式二分探索のさらなる利点

めぐるちゃんのツイートにも書いてあることですが、上の状態でもまだ

  • left は常に条件を満たさない
  • right は常に条件を満たす
  • right - left = 1 になるまで範囲を狭める (最後は right が条件を満たす最小)

という部分で、left と right のどちらが条件を満たしていたかを考える部分に思考リソースをとられます。また上記は「条件を満たす最小の index を求める」という処理でしたが、代わりに以下のようにして「条件を満たす最大の index を求める」という風にしたくなる場面もあります。

  • left は常に条件を満たす
  • right は常に条件を満たさない
  • right - left = 1 になるまで範囲を狭める (最後は left が条件を満たす最大)

めぐる式二分探索ではそれも含めた統一的な実装を可能にしています。left と right のどちらが大きいかも気にすることなく、以下のように書くことができます。

#include <iostream>
#include <vector>
using namespace std;

vector<int> a = {1, 14, 32, 51, 51, 51, 243, 419, 750, 910};

// index が条件を満たすかどうか
bool isOK(int index, int key) {
    if (a[index] >= key) return true;
    else return false;
}

// 汎用的な二分探索のテンプレ
int binary_search(int key) {
    int ng = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    int ok = (int)a.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

    /* ok と ng のどちらが大きいかわからないことを考慮 */
    while (abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;

        if (isOK(mid, key)) ok = mid;
        else ng = mid;
    }
    return ok;
}

int main() {
    cout << binary_search(51) << endl; // a[3] = 51 (さっきは 4 を返したが今回は「最小の index」なので 3)
    cout << binary_search(1) << endl; // a[0] = 1
    cout << binary_search(910) << endl; // a[9] = 910

    cout << binary_search(52) << endl; // 6
    cout << binary_search(0) << endl; // 0
    cout << binary_search(911) << endl; // 10 (場外)
}

ここまで来れば、二分探索処理の実装にとられる思考リソースをかなり軽減できると思います。

4. 一般化した二分探索の適用例

4-1. 年齢当てゲーム

まずは

でも挙げた年齢当てゲームを考えてみましょう。問題設定を再掲します。

A さんの年齢を当てようとしています。
A さんが、20 歳以上 36 歳未満だというのはわかっているとしましょう。あなたは A さんに 4 回だけ Yes / No で答えられる質問をすることができます。A さんの年齢を当てられるでしょうか？？？

年齢当てゲームの実装

20 歳以上 36 歳未満であることはわかっている A さんの年齢を 4 回の質問でズバリ当てます！

以下の実装のキーとなる変数 left, right についてですが、

  • x = left は「A さんの年齢は x 歳以上である」という条件を満たす
  • x = right は「A さんの年齢は x 歳以上である」という条件を満たさない

という状態を常に保つようにしています。言い換えれば、A さんの年齢の候補が常に left 歳以上 right 歳未満となるように定めています。初期状態は left = 20, right = 36 と 16 歳分の幅がありますが、質問を通して狭めて行きます。終了状態では right - left = 1 となっていて、A さんは left 歳以上 right 歳未満なので left 歳で確定します。

なお、上の年齢当てゲームでは簡単のために right - left が 2 の冪乗 (2^4 = 16) になるようにしていましたが、そうでなくても下の実装はきちんと動作します。例えば left = 0, right = 100 としてもきちんと動作します (その場合は最大で 7 回の質問で当てます)。

#include <iostream>
using namespace std;

int main() {
    cout << "Start Game!" << endl;

    /* A さんの年齢の候補を表す区間を、[left, right) と表します */
    /* A さんは、left 歳以上 right 歳未満、right 歳自体は候補に含まれないことに注意 */
    int left = 20, right = 36;

    /* A さんの年齢を 1 つに絞れないうちは繰り返す */
    while (right - left > 1) {
        int mid = left + (right - left) / 2; // 区間の真ん中

        /* mid 歳以上かを聞いて、回答を yes/no で受け取る */
        cout << "Is the age same or more than " << mid << " ? (yes / no)" << endl;
        string ans;
        cin >> ans;

        /* 回答の応じて、年齢を絞る */
        if (ans == "yes") left = mid; // mid 歳以上なら、mid 歳以上 right 歳以下になるように
        else right = mid; // mid 歳未満なら、left 歳以上 mid 歳未満になるように
    }

    /* ズバリ当てる！ */
    cout << "The age is " << left << "!" << endl;
}
719
562
6

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
719
562