バイナリナビゲーションとは？

本ブログ作成文は、講義を目指して製作されました。 また、作成された文章の情報も間違っている可能性がありますので、ご注意ください。

Binary Search（バイナリサーチ）は、ソートされた範囲の中央値を確認し、サーチ区間を半分減らします。

1 3 5 7 9 11 13
↑7確認

11を見つけるには、右半分だけ残します。

基本的な実装

int BinarySearch(const std::vector<int>& Values, int Target)
{
    int Left = 0;
    int Right = static_cast<int>(Values.size()) - 1;

    while (Left <= Right)
    {
        const int Middle = Left + (Right - Left) / 2;

        if (Values[Middle] == Target)
        {
            return Middle;
        }

        if (Values[Middle] < Target)
        {
            Left = Middle + 1;
        }
        else
        {
            Right = Middle - 1;
        }
    }

    return -1;
}

毎回範囲が半分になるので、時間の複雑さはO(log N)である。

必ず整列されなければならない

ソートされていないデータにバイナリ検索を適用すると、どの半分を捨ててもよいかを判断することはできません。 探索するたびに最初にソートする場合は、ソートコストも同様に計算する必要があります。

最初の同じ値、最後の同じ値、値が入る位置を見つける問題は、境界条件が少しずつ異なります。 C++ではstd::lower_boundとstd::upper_boundを使用すれば、このような境界を安全に求めることができる。

バイナリ探索の難しい部分は、中央値を見つけることではありません。 現在の範囲が閉じた区間か半開区間か最後まで同じ規則を維持するのだ。