二分探索アルゴリズム：効率的な検索手法をわかりやすく解説

はじめに

現代社会において、膨大なデータの中から必要な情報を見つけ出すことは、私たちの生活のあらゆる場面で必要不可欠です。オンラインショッピングで商品を探したり、図書館で本を探したり、膨大な顧客データから特定の顧客を見つけ出したりと、効率的な検索は時間と労力を節約する上で非常に重要です。このような効率的な検索を実現するアルゴリズムの一つが、二分探索アルゴリズムです。

二分探索は、ソート済みのデータ集合に対して適用できる、非常に高速な検索アルゴリズムです。例えば、250万個以上の星に関する情報を含むTycho-2星表から特定の星の名前を検索する場合を考えてみましょう。単純に最初から順番に星を調べていく方法 (線形探索)では、最悪の場合、250万個すべての星を調べる必要があります。しかし、星表が星の名前でアルファベット順にソートされている場合、二分探索を用いることで、最悪でもわずか22個の星を調べるだけで目的の星を見つけることができます。

この記事では、二分探索の基本的な考え方から、具体的な例、さらには応用方法までを、図解を交えながらわかりやすく解説していきます。初心者の方でも理解しやすいように、専門用語はできるだけ避け、段階的に解説を進めていきます。また、プログラマーの方にも役立つ情報として、計算量や実装方法についても詳しく説明します。

二分探索とは？
二分探索の仕組み
二分探索の計算量
二分探索の長所と短所
二分探索の例
二分探索の応用
様々なデータ構造における二分探索
二分探索の実装
まとめ
たび友｜サイトマップ

二分探索とは？

二分探索 (binary search) とは、ソート済み のデータ集合の中から、特定の値を探索するアルゴリズムです。データ集合がソート済みであるという前提を利用することで、探索範囲を効率的に絞り込み、高速に目的の値を見つけることができます。これは、「分割統治法」と呼ばれる問題解決手法の一例です。

二分探索の仕組み

二分探索の仕組みを、人間相手に説明する例えとして、1から100までの数字の中から、特定の数字を当てるゲームを考えてみましょう。

まず、あなたは50を予想します。
相手は、その数字が大きすぎるか、小さすぎるか、または正解かを教えてくれます。
もし50より大きければ、次は51から100の間の数字を予想します。
もし50より小さければ、次は1から49の間の数字を予想します。

このように、毎回探索範囲を半分に絞り込むことで、効率的に目的の数字にたどり着くことができます。

これを、配列のようなデータ構造に当てはめて考えてみましょう。

探索範囲の中央の値を調べる: ソート済みのデータ集合の中央にある値を調べます。
目的の値と比較する: 中央の値と目的の値を比較します。
探索範囲を絞り込む:
- 中央の値が目的の値よりも大きい場合、目的の値は中央の値よりも左側にあるので、探索範囲を左半分に絞り込みます。
- 中央の値が目的の値よりも小さい場合、目的の値は中央の値よりも右側にあるので、探索範囲を右半分に絞り込みます。
- 中央の値が目的の値と等しい場合、探索は成功し、その位置を返します。
繰り返す: 探索範囲が空になるか、目的の値が見つかるまで、上記のステップを繰り返します。

例

1から10までの数字が並んだ配列から、7を二分探索で探してみましょう。

中央の値 (5) を調べます。 7は5より大きいので、探索範囲を右半分に絞り込みます。
探索範囲の中央の値 (8) を調べます。 7は8より小さいので、探索範囲を左半分に絞り込みます。
探索範囲の中央の値 (7) を調べます。 7と等しいので、探索は成功です。

二分探索の計算量

二分探索の計算量は、O(log n) です。ここで、n はデータ集合の要素数です。

これは、探索のたびに探索範囲が半分になるため、探索回数が log n に比例することを意味します。そのため、データ集合の要素数が非常に大きくても、高速に探索を行うことができます。

例えば、100万個の要素を持つデータ集合から目的の値を探索する場合、最大でも約20回の比較で探索が完了します (log₂1,000,000 ≈ 20)。一方、線形探索では、最悪の場合、100万回の比較が必要となります。このように、二分探索は線形探索に比べて、特にデータ集合が大きい場合に、非常に効率的です。

二分探索の長所と短所

二分探索は、高速な検索アルゴリズムですが、万能ではありません。ここでは、二分探索の長所と短所をまとめます。[参考]

長所

効率性: ソート済みのデータに対して非常に効率的であり、大規模なデータセットでも高速に検索できます。
実装の容易さ: アルゴリズムが比較的単純で、理解しやすく実装しやすいです。
汎用性: 様々なデータ構造に適用できます。
信頼性: 目的の要素が存在する場合、必ずそれを探し出すことができます。

短所

ソート済みデータ: 二分探索は、ソート済みのデータにしか適用できません。
ソートのコスト: データがソートされていない場合、事前にソートする必要がありますが、ソートには計算コストがかかります。
動的なデータ: データが頻繁に更新される場合、ソート状態を維持することが困難になる可能性があります。

二分探索の例

二分探索は、以下のような様々な場面で利用されています。

例	説明
辞書	辞書で単語を検索する際に、二分探索のような方法を用いることで、目的の単語を素早く見つけることができます。
電話番号帳	電話番号帳で名前から電話番号を検索する際にも、二分探索が役立ちます。
プログラミング	プログラミングにおいては、配列やリストなどのデータ構造から特定の値を検索する際に、二分探索が頻繁に利用されます。

二分探索の応用

二分探索は、基本的なアルゴリズムですが、様々な応用が可能です。

平方根の近似値を求める: 二分探索を用いることで、平方根の近似値を効率的に求めることができます。これは、与えられた数 x に対し、x の平方根となるような数 y を探索する問題として捉えることができます。
ゲーム開発: ゲーム開発においては、衝突判定や経路探索などに二分探索が利用されます。例えば、ゲーム空間内でプレイヤーキャラクターとオブジェクトが衝突したかどうかを判定する際に、二分探索を用いて効率的に判定することができます。
データベース: データベースにおいては、インデックスを用いた高速なデータ検索に二分探索が利用されます。インデックスは、データベース内のデータを高速に検索するためのデータ構造であり、二分探索を用いることで、インデックスから目的のデータを効率的に探し出すことができます。
様々な二分探索: 二分探索は、様々なバリエーションがあります。例えば、一様二分探索は、データが均等に分布している場合に用いられる手法で、探索範囲を半分にするのではなく、目的の値がどのあたりに存在するかを推定して探索を行います。 指数探索は、データの範囲がわからない場合に用いられる手法で、探索範囲を指数関数的に広げていき、目的の値を含む範囲を見つけ出してから二分探索を行います。 補間探索は、データの分布を考慮して探索範囲を絞り込む手法で、線形補間を用いて目的の値がどのあたりに存在するかを推定します。

様々なデータ構造における二分探索

二分探索は、配列だけでなく、様々なデータ構造に適用することができます。その代表例が、二分探索木です。二分探索木は、各ノードが最大で2つの子ノードを持つ木構造であり、左の子ノードの値は親ノードの値よりも小さく、右の子ノードの値は親ノードの値よりも大きくなるように構成されています。このような構造を持つ二分探索木に対して二分探索を行うことで、効率的にノードを検索することができます。

二分探索の実装

二分探索は、反復 (iterative) と再帰 (recursive) の2つの方法で実装することができます。

反復による実装 (Python)

Python

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0

    while low <= high:
        mid = (high + low) // 2

        if arr < x:
            low = mid + 1

        elif arr > x:
            high = mid - 1

        else:
            return mid

    return -1 # 見つからなかった場合

再帰による実装 (Python)

Python

def binary_search_recursive(arr, low, high, x):
    if high >= low:
        mid = (high + low) // 2

        if arr == x:
            return mid

        elif arr > x:
            return binary_search_recursive(arr, low, mid - 1, x)

        else:
            return binary_search_recursive(arr, mid + 1, high, x)

    else:
        return -1 # 見つからなかった場合