二分探索（binary search）

• テクノロジ系
• アルゴリズムとプログラミング
• 基本情報
• 応用情報
• 重要度 ★★★★☆

もう少し詳しい説明

二分探索は、探す範囲を毎回半分に減らしていく探し方です。

辞書で単語を引くときを思い浮かべてください。「か」で始まる語を探すのに、1ページ目からめくる人はいません。だいたい真ん中を開いて、行きすぎたか手前かを見て、その半分をまるごと無視します。あれと同じ考え方です。

真ん中と比べて、探すものが小さければ右半分はもう見なくていい。大きければ左半分を見なくていい。1回比べるたびに、候補が半分になります。

前提：並んでいること

ここが大事な条件です。二分探索は、データが順番に並んでいるときにしか使えません。

真ん中と比べて「こっち側にはもう無い」と言い切れるのは、並んでいるからです。ばらばらに置かれていたら、真ん中より小さいものが右側にあるかもしれず、片側を捨てられません。

だから試験では、「整列済みの」という言葉が問題文に必ず入ります。この一言があれば二分探索、無ければ線形探索の話だと判断できます。

どれくらい速いのか

端から1件ずつ見ていく方法を線形探索と呼びます。比べてみます。

100万件でも20回です。件数が1,000倍になっても、比較の回数は2倍にしかなりません。ここが二分探索の威力で、データが増えるほど差が開きます。

何回で見つかるかの求め方

試験では回数を計算させる問題が出ます。考え方は単純で、**「2を何回かけたらその件数になるか」**です。

1,024件なら、2 を 10 回かけると 1,024（2¹⁰ ＝ 1,024）なので、最大10回です。数学の記号で書けば log₂1,024 ＝ 10 で、これが計算量 O(log n) の正体です。

よく出る件数は覚えておくと速く解けます。

2¹⁰ ＝ 1,024 ≒ 1,000 だけ覚えておけば、そこから倍々で伸ばせます。

万能ではない

速いのですが、弱点もあります。

• 並べておく手間がかかる。 並べ替え自体に時間がかかるので、1回しか探さないなら割に合わないことがあります
• データの追加が重い。 途中に1件足すだけで、並び順を保つために後ろをずらす必要があります

そのため、何度も探すが、あまり書き換えないデータに向いています。データベースの索引（インデックス）が速いのも、この考え方によります。

試験ではこう出る

科目A（旧・午前）のアルゴリズム分野で頻出です。多いのは、件数を示して最大の比較回数を答えさせる計算問題と、線形探索と並べて計算量を選ばせる問題です。応用情報や科目Bでは、実際に探索が進む様子を1回ずつ追わせ、何回目で見つかるかを答えさせる形になります。

引っかかりやすいのは、「整列済み」という条件を見落とすことです。並んでいないデータに二分探索は使えないので、「整列されていないデータを二分探索する」と書いてある選択肢は、それだけで誤りだと判断できます。回数の計算は、件数を2で割り続けて1になるまでの回数を数えるのが、公式を忘れたときの確実な戻り方です。

関連する用語

線形探索

端から1件ずつ順に見ていく探し方。並んでいなくても使えるが遅い

計算量

データが増えたときに処理時間がどう伸びるかの指標。二分探索は O(log n)

インデックス

検索を速くする索引。並べておいて半分ずつ絞る、という考え方は同じ

整列（ソート）

データを順番に並べ替えること。二分探索は、これが済んでいることが前提

スタック

後に入れたものから先に取り出すデータ構造

ミニクイズ

最終更新：2026-09-16