---
title: "二分探索とは？整列済みデータを半分ずつ絞り込む探索方法【基本情報技術者試験】"
description: "二分探索を整列済みデータを半分ずつ絞り込んで探す方法として整理し、線形探索との違い、計算量、科目Bの擬似言語問題での読み方をやさしく解説します。"
last_modified_at: "2026-06-23"
canonical_url: "https://stemtazoo.github.io/fe/binary-search/"
section: "fe"
---

## まず結論

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

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

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

## 直感的な説明

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

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

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

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

を判断します。

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

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

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

## 定義・仕組み

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

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

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

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

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

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

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

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

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

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

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

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

## 科目Aでどう出る？

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

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

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

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

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

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

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

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

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

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

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

## 科目Bでどう使う？

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

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

```text
left
right
mid
low
high
中央
上限
下限
```

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

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

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

```text
mid = (left + right) / 2
```

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

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

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

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

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

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

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

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

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

## よくある誤解・混同

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

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

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

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

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

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

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

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

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

## まとめ（試験直前用）

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