二分探索アルゴリズムと例

二分探索を学ぶ前に、まず探索とは何かを学びましょう。

検索とは何ですか?

検索は、ユーザーがデータベース内に保持されているドキュメント、ファイル、メディア、またはその他の種類のデータを検索できるようにするユーティリティです。 検索は、基準とレコードを照合し、それをユーザーに表示するという単純な原理に基づいて機能します。 このようにして、最も基本的な検索機能が機能します。

二分探索とは何ですか？

バイナリサーチは、ソートされたアイテムのリストからデータを見つけて取得する高度な検索アルゴリズムです。その基本的な動作原理は、必要な値が見つかり、検索結果としてユーザーに表示されるまで、リスト内のデータを半分に分割することです。バイナリサーチは一般的に、 半間隔検索 または 対数検索.

二分探索はどのように機能するのでしょうか?

バイナリ検索は次のように動作します。

• 検索プロセスは、ソートされたデータ配列の中央の要素を見つけることから開始されます。
• その後、キーの値が要素と比較されます。
• キー値が中央の要素よりも小さい場合、検索では中央の要素よりも大きい値を比較して照合します。
• キー値が中央の要素より大きい場合、検索では中央の要素までのより小さい値を分析し、比較および照合を行います。

二分探索アルゴリズム（擬似コード）

二分探索は、短い反復ルーチンとして記述できます。このルーチンは、lowとhighという2つのポインタを保持し、ターゲットが見つかるか範囲が空になるまで範囲を絞り込んでいきます。

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

このルーチンは、成功した場合は対象のインデックスを返し、値が存在しない場合は -1 を返します。範囲はパスごとに半分になるため、ループは最大で log₂(n) 回実行されます。

二分探索の例

辞書の例を見てみましょう。特定の単語を探す必要がある場合、各単語を順番に調べるのではなく、最も近い単語をランダムに探して必要な単語を検索します。

上の画像は、次のことを示しています。

1. 10 桁の配列があり、要素 59 を見つける必要があります。
2. すべての要素には、0から9までのインデックスが付けられています。次に、配列の中央値を計算します。そのためには、インデックスの左端と右端の値を取り、それらを2で割ります。結果は4.5ですが、切り捨て値を使用します。したがって、中央値は4です。
3. このアルゴリズムは、中央（4）から最小値までのすべての要素を削除します。なぜなら、59は24より大きいからです。その結果、配列には5つの要素だけが残ります。
4. さて、59は45より大きく、63より小さい。中央値は7である。したがって、右インデックス値は中央値－1となり、6となる。左インデックス値は以前と同じ5のままである。
5. この時点で、59 の後に 45 が来ることがわかります。したがって、左側のインデックス (5) も Mid になります。
6. これらの繰り返しは、配列が XNUMX つの要素のみに減らされるか、検索される項目が配列の中央になるまで続きます。

例

二分探索の仕組みを理解するために、次の例を見てみましょう。

1. 2 ～ 20 の範囲で並べ替えられた値の配列があり、18 を見つける必要があります。
2. 下限値と上限値の平均は (l + r) / 2 = 4 です。検索対象の値は中間値である 4 よりも大きいです。
3. 配列の値が中央値より小さい場合は検索対象から除外され、中央値である4より大きい値が検索対象となります。
4. これは、実際の検索対象が見つかるまで繰り返し分割されるプロセスです。

なぜ二分探索が必要なのでしょうか?

バイナリサーチを検索アルゴリズムとして使用するのに適した理由は以下のとおりです。

• 二分探索は、データのサイズに関係なく、ソート済みのデータに対して効率的に機能します。
• データを順番に調べて検索を実行する代わりに、バイナリ アルゴリズムはデータにランダムにアクセスして必要な要素を見つけます。 これにより、検索サイクルが短縮され、より正確になります。
• 二分探索は、等価比較を用いるのではなく、順序付けの原則に基づいてソートされたデータの比較を行います。等価比較は処理速度が遅く、ほとんどの場合不正確です。
• アルゴリズムは、検索の各サイクル後、配列のサイズを半分に分割します。そのため、次の反復処理では、残りの半分の配列のみを処理することになります。

次のチュートリアルでは、 線形探索: Python, C++ 例:.

二分探索と線形探索の比較

コレクション内の値を検索する最も一般的な方法は、二分探索と線形探索の2つです。以下の表は、これらの違いをまとめたものです。

要するに、二分探索は大規模でソート済みのデータに対してははるかに高速ですが、線形探索はより単純で、データがソートされていない場合は唯一の選択肢となります。

よくあるご質問