最終更新日：2026年6月23日

fe fe-technology algorithm data-structure

まず結論

二分探索とは、整列済みのデータを対象に、探索範囲を半分ずつ狭めて目的の値を探す方法です。

基本情報技術者試験では、線形探索との違いがよく問われます。

判断のポイントは、二分探索は整列済みであることが前提という点です。

直感的な説明

二分探索は、辞書で言葉を探すイメージです。

例えば、五十音順に並んだ辞書で「やま」を探すとします。

最初から1ページずつ見るのではなく、真ん中あたりを開いて、

目的の言葉は、今見ているページより前か？
それとも後ろか？

を判断します。

目的の言葉が後ろにあると分かれば、前半はもう探さなくてよくなります。

このように、候補を一気に半分に減らしていくのが二分探索です。

英語では binary search と呼ばれます。
binary は「2つに分ける」というイメージで押さえると分かりやすいです。

定義・仕組み

二分探索では、整列された配列などを対象に、中央の値と目的の値を比較します。

基本的な流れは次のとおりです。

1. 探索範囲の中央の要素を見る
2. 中央の値が目的の値なら探索を終了する
3. 目的の値が中央より小さければ、左側だけを探す
4. 目的の値が中央より大きければ、右側だけを探す
5. 見つかるまで、探索範囲を半分ずつ狭める

例えば、次のように昇順に整列された配列があるとします。

a[0] = 2
a[1] = 5
a[2] = 8
a[3] = 12
a[4] = 16
a[5] = 23
a[6] = 38

ここから 16 を探す場合、まず中央付近の値を見ます。

中央 a[3] = 12
16 は 12 より大きい
→ 左側は探さず、右側だけを見る

次に右側の範囲から中央を見ます。

a[5] = 23
16 は 23 より小さい
→ 23 より右側は探さない

さらに範囲を絞ると、a[4] = 16 が見つかります。

このように、二分探索は一つずつ見るのではなく、範囲を減らしながら探します。

二分探索は、基本情報技術者試験の「アルゴリズムとプログラミング」や、整列済み配列などの「データ構造」と関係が深いテーマです。公式の出題範囲は、IPA：基本情報技術者試験 から確認できるシラバスで確認できます。

科目Aでどう出る？

科目Aでは、二分探索の特徴や計算量が問われやすいです。

特に見るべきポイントは次の3つです。

  • 整列済みのデータが前提
  • 中央の値と比較して探索範囲を半分にする
  • 線形探索より少ない比較回数で済みやすい

例えば、次のような説明は二分探索の説明として自然です。

整列済みの配列について、中央の値と比較しながら探索範囲を半分ずつ狭める。

一方で、次の説明は線形探索です。

先頭から順に目的の値と一致するか確認する。

二分探索の計算量は、一般に O(log n) と表されます。

ただし、FEでは記号だけを覚えるより、次のように理解しておくと判断しやすいです。

線形探索：データ数が増えると、確認回数も増えやすい
二分探索：1回比較するたびに、候補が半分になる

データ数が多いほど、二分探索の効率の良さが出やすくなります。

科目Bでどう使う？

科目Bでは、二分探索は擬似言語の読み取りで出ることがあります。

特に、次のような変数が出てきたら、二分探索の可能性があります。

left
right
mid
low
high
中央
上限
下限

読むときは、変数名そのものより、役割を見るのが大切です。

役割 よくある変数名
探索範囲の左端 left, low
探索範囲の右端 right, high
中央位置 mid

二分探索の擬似言語では、中央位置を次のように求めることがあります。

mid = (left + right) / 2

そして、中央の値と探す値を比較します。

a[mid] が目的の値より小さい
→ left を mid より右に動かす

a[mid] が目的の値より大きい
→ right を mid より左に動かす

ここで大切なのは、どちら側を捨てているかを追うことです。

科目Bでは、次の順で読むと整理しやすいです。

  1. 配列が昇順か降順かを見る
  2. 探索範囲の左端・右端を確認する
  3. 中央位置を確認する
  4. 中央の値と目的の値を比較する
  5. left と right のどちらが更新されるかを見る

特に、昇順と降順で条件の意味が変わることに注意します。

昇順なら、目的の値が中央より大きい場合は右側を探します。
降順なら、同じ考え方をそのまま当てはめると間違えることがあります。

問題文の並び順を先に確認するのが安全です。

よくある誤解・混同

二分探索で一番多い誤解は、どんな配列にも使えると思ってしまうことです。

二分探索は、基本的に整列済みデータが前提です。

整列されていない配列に対して、中央の値を見ても、目的の値が左側にあるのか右側にあるのか判断できません。

探索方法 探し方 整列の必要
線形探索 先頭から順番に探す 不要
二分探索 半分ずつ範囲を狭める 必要

試験では、次のように切り分けると分かりやすいです。

  • 整列されていない → 線形探索が使える
  • 整列済み → 二分探索が使える可能性がある
  • 半分ずつ範囲を狭める → 二分探索

また、「二分探索は必ず最初に見つかる」と考えるのも誤りです。

二分探索は効率よく範囲を絞る方法ですが、目的の値が存在しない場合もあります。

その場合は、探索範囲がなくなった時点で「見つからない」と判断します。

まとめ（試験直前用）

  • 二分探索は、整列済みデータを半分ずつ絞り込んで探す方法
  • 中央の値と目的の値を比較する
  • 線形探索との最大の違いは、整列が前提かどうか
  • 科目Bでは left・right・mid の更新を追う
  • 判断に迷ったら「半分ずつ捨てているか」を見る

© 2024-2026 stemtazoo. All rights reserved.