Zenn
🗡️

【Python】二分探索法の実装と仕組み

に公開
Python
二分探索
tech

初めに

二分探索法の実装と仕組みについて、改めてまとめてみようと思いこの記事を書いています。
今回は実装においては、ループ（反復処理） を使った実装でやっています。

二分探索法とは

ソートされた（昇順または降順に並べられた）データの配列の中から、特定の要素を探し出す際に有効なアルゴリズムです。二分探索法の根本的な考え方は、「分割統治」 という考え方にあります。これは、問題を小さな部分問題に分割し、それぞれを解決することで全体の解を導き出す手法です。
具体的には、以下の手順を繰り返します。

  1. 探索範囲の中央にある要素に着目する。
  2. その中央の要素と、探している値を比較する。
  3. 比較結果に基づいて、探索範囲を半分に絞り込む。

メリット

  • 非常に高速な検索が可能で、探索範囲を毎回半分に絞り込むため、データ量が多くなっても検索にかかる時間が劇的に短くなります

デメリット

  • データがソートされている必要があります。
  • 配列の中央の要素にアクセスしたり、探索範囲を更新したりする性質上、連結リストのようなデータ構造には効率的に適用できません。

実装

二分探索法の手順について、具体的なステップを以下にまとめます。

  1. 探索範囲の初期化
    • 探索範囲の左端（low）を 配列の最初のインデックス（0）に設定
    • 探索範囲の右端（high）を 配列の最後のインデックス（len(array) - 1）に設定
  2. 中央の要素の特定
    • 中央のインデックス（mid）を計算する
  3. 値の比較
    • 一致する場合→中央の要素が目的の値と一致したら、そのインデックスを返して探索終了
    • 目的の値が小さい場合→探索値は中央の左側にあるので、探索範囲を左に狭める
    • 目的の値が大きい場合→探索値は中央の右側にあるので、探索範囲を右に狭める
  4. 繰り返し処理
  • low <= high の間、ステップ2と3を繰り返す
  1. 探索失敗の時の処理

実際にPythonで実装してみる

def binary_search(target, array): #target は探したい値。array は ソート済み の配列。
    low = 0 #探索範囲の 左端（最小インデックス） を 0 に初期化。
    high = len(array) - 1

    while low <= high:
        mid = (low + high) // 2
        if array[mid] == target:
            return mid
        elif array[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

テストしてみる。

今回は、assertを使用していきたいと思います。以下に簡単にassertの使い方をまとめます。
基本構文

assert 条件式
  • 条件式が True なら → 何も起きず、処理はそのまま進みます。
  • 条件式が False なら → AssertionError という例外が発生し、プログラムが停止します。

テスト項目

以下における正常系、異常系においてテストします。

  • 空配列・要素数1
  • 奇数長配列 [1, 3, 5] に対する探索
  • 偶数長配列 [1, 3, 5, 7] に対する探索

実際に書いてみる

def test_binary_search():
    assert binary_search(3, []) == -1
    assert binary_search(3, [1]) == -1
    assert binary_search(1, [1]) == 0

    assert binary_search(1, [1, 3, 5]) == 0
    assert binary_search(3, [1, 3, 5]) == 1
    assert binary_search(5, [1, 3, 5]) == 2
    assert binary_search(0, [1, 3, 5]) == -1
    assert binary_search(2, [1, 3, 5]) == -1
    assert binary_search(4, [1, 3, 5]) == -1
    assert binary_search(6, [1, 3, 5]) == -1

    assert binary_search(1, [1, 3, 5, 7]) == 0
    assert binary_search(3, [1, 3, 5, 7]) == 1
    assert binary_search(5, [1, 3, 5, 7]) == 2
    assert binary_search(7, [1, 3, 5, 7]) == 3
    assert binary_search(0, [1, 3, 5, 7]) == -1
    assert binary_search(2, [1, 3, 5, 7]) == -1
    assert binary_search(4, [1, 3, 5, 7]) == -1
    assert binary_search(6, [1, 3, 5, 7]) == -1
    assert binary_search(8, [1, 3, 5, 7]) == -1

    print("✅ All tests passed.")

test_binary_search()

まとめ

今回は、二分探索法の基本的な概念から、ループを使った具体的な実装、そして効果的なテスト方法までを解説しました。

  • 二分探索法は「ソート済み配列」に対して効率的に探索できるアルゴリズムで、毎回探索範囲を半分に絞り込むことで高速に目的の要素を見つけられます。
  • 実装では、探索範囲の左右端を管理しながら中央の要素と比較し、探索範囲を更新するループ処理を行います。

Discussion