基本情報 科目B 二分探索のトレース練習
基本情報技術者試験の科目Bで、線形探索の次に必ず出会うのが 二分探索（バイナリサーチ） です。出題頻度が高い一方で、lo（下端）・hi（上端）・mid（中央）という 3 つの変数を同時に動かす ため、「今どこを見ているのか分からなくなる」と最もつまずきやすいアルゴリズムでもあります。本記事は、二分探索を変数の値を表に書きながら 1 行ずつ追う トレース で攻略する練習帳です。合計・最大値・線形探索のトレース練習 の続編として、見つかる場合・見つからない場合の両方を実演します。
本記事は 過去問AI が学習用に作成したオリジナルの例題です。掲載している擬似言語は IPA の過去問・公式サンプルの転載ではなく、説明用に書き起こしたものです。擬似言語の正式な記述形式は必ず IPA 公式ページ で確認してください。記法そのものの読み方は 基本情報 科目Bの擬似言語 記法早見表 にまとめています。
二分探索は「半分に絞り込む」検索
線形探索が先頭から 1 つずつ調べるのに対し、二分探索は 真ん中を見て、探したい値がそれより大きいか小さいかで、調べる範囲を半分に捨てていく 検索です。1 回比べるごとに候補が半分になるので、要素数が大きいほど劇的に速くなります。たとえば 1,000 個の配列でも、線形探索なら最悪 1,000 回比べるところを、二分探索は約 10 回（2 の 10 乗が 1,024）で済みます。
ただし二分探索には 絶対の前提条件 があります。
- 配列が並べ替え済み（昇順または降順にソート済み）であること。並んでいない配列に二分探索は使えません
- 本記事では昇順（小さい順）にソート済みの配列を前提にします
この記事の例題は、すべて次の約束ごとで進めます（科目Bの標準的なルールです）。
- 代入は ←（右の値を左の変数に入れる）。条件式の中の ＝ は「等しいか？」の比較
- 配列の 要素番号は 1 から始まる。A[1] が先頭、A[要素数] が末尾
- mid ← (lo + hi) ÷ 2 の ÷ は 商の整数部分（小数点以下は切り捨て）。例：(1 + 7) ÷ 2 = 4、(1 + 3) ÷ 2 = 2、(5 + 5) ÷ 2 = 5
記法そのものが不安なら、先に 記法早見表 で ← や ÷ の扱いを確認してから戻ってくるとスムーズです。
例題のコード
昇順にソート済みの配列 A = {2, 5, 8, 11, 14, 17, 20}（要素数 7）から、値 key を探して 何番目にあるか を返すコードです。
整数型: lo ← 1
整数型: hi ← 7
整数型: mid
整数型: 位置 ← -1
while ((lo ≦ hi) and (位置 = -1))
mid ← (lo + hi) ÷ 2
if (A[mid] = key)
位置 ← mid
elseif (A[mid] < key)
lo ← mid + 1
else
hi ← mid - 1
endif
endwhile
読み方はこうです。lo と hi で「今調べている範囲の下端と上端」を表し、その真ん中 mid を見ます。A[mid] が key と一致すれば位置を記録して終了。A[mid] が key より小さければ、答えは mid より 右 にあるので下端を lo ← mid + 1 と上げる。逆に大きければ、答えは mid より 左 なので上端を hi ← mid - 1 と下げる。これを範囲がある（lo ≦ hi）かつ未発見（位置 = -1）の間だけ繰り返します。
例1：見つかる場合（key = 14 を探す）
トレース表には、ループが 1 周するごとに lo・hi・mid・A[mid]・比較結果・更新後の (lo, hi)・位置 を書きます。
| ループ回 | lo | hi | mid | A[mid] | 判定 | 更新後 (lo, hi) | 位置 |
|---|---|---|---|---|---|---|---|
| 開始前 | 1 | 7 | − | − | − | (1, 7) | -1 |
| 1周目 | 1 | 7 | 4 | 11 | 11 < 14 → 右へ | lo ← 5 で (5, 7) | -1 |
| 2周目 | 5 | 7 | 6 | 17 | 17 > 14 → 左へ | hi ← 5 で (5, 5) | -1 |
| 3周目 | 5 | 5 | 5 | 14 | 14 = 14 → 一致 | 位置 ← 5 | 5 |
3 周目で A[5] = 14 が key と一致し、位置に 5 を記録します。次に継続条件 (lo ≦ hi) and (位置 = -1) を見ると、位置が 5（≠ -1）なので 偽 になり、ループが終わります。答えは 位置 = 5（14 は配列の 5 番目）。
注目すべきは 範囲の絞り込み方 です。1 周目で「11 より右」と分かった瞬間、左半分（A[1]〜A[4]）はもう二度と見ません。これが半分ずつ捨てる動きで、線形探索なら 5 回かかる検索が 3 回で終わっています。
例2：見つからない場合（key = 10 を探す）
配列に存在しない値を探すと、二分探索がどう「無い」と判断するかが分かります。
| ループ回 | lo | hi | mid | A[mid] | 判定 | 更新後 (lo, hi) | 位置 |
|---|---|---|---|---|---|---|---|
| 開始前 | 1 | 7 | − | − | − | (1, 7) | -1 |
| 1周目 | 1 | 7 | 4 | 11 | 11 > 10 → 左へ | hi ← 3 で (1, 3) | -1 |
| 2周目 | 1 | 3 | 2 | 5 | 5 < 10 → 右へ | lo ← 3 で (3, 3) | -1 |
| 3周目 | 3 | 3 | 3 | 8 | 8 < 10 → 右へ | lo ← 4 で (4, 3) | -1 |
| 判定 | 4 | 3 | − | − | lo > hi → 終了 | − | -1 |
3 周目で lo が 4、hi が 3 になり、lo > hi（下端が上端を追い越した）状態になりました。これは「調べる範囲が無くなった」という意味で、継続条件 (lo ≦ hi) が偽になりループ終了。位置は最初の -1 のまま変わらず、「key は配列に無い」と分かります。線形探索と同じく、ありえない値 -1 を初期値にしておき、最後まで変わらなければ未発見 と判断するパターンです。
つまずきやすい3つのポイント
- mid は整数除算で切り捨て。(lo + hi) ÷ 2 で小数が出たら必ず切り捨てます。(1 + 2) ÷ 2 は 1.5 ではなく 1。ここを四捨五入すると以降の値が全部ずれます。
- lo ← mid + 1 / hi ← mid - 1 の「±1」を忘れない。mid 自身はもう調べ済みなので、次の範囲から mid を外す ために +1 / -1 します。これを lo ← mid のように書くと、範囲が縮まらず 無限ループ になる危険があります。
- そもそもソート済みか確認する。二分探索は並べ替え済みの配列にしか使えません。問題文で「昇順に整列されている」などの条件を必ずチェックしてください。並んでいなければ線形探索を使います。
トレースで詰まらないためのコツ
二分探索は変数が 3 つに増えるぶん、表の 列を最初に lo・hi・mid・位置 と決めてしまう のが最大のコツです。あとは 1 行進むごとに、変わった変数だけ書き換えていけば、頭で覚えなくても確実に追えます。範囲 (lo, hi) を毎回書いておくと、「今どこを見ているか」が一目で分かり、迷子になりません。
次のステップ
二分探索が追えるようになったら、出題範囲のアルゴリズムを一通りトレースで体験するのが近道です。基礎の 合計・最大値・線形探索のトレース練習 をまだ見ていなければ先にそちらを、並べ替えの定番は ソート（整列）のトレース練習 で選択ソートを二重ループのまま 1 行ずつ追えます。読む速度を上げる訓練法は 基本情報科目B｜擬似言語アルゴリズム読解の3ステップ訓練法 で扱っています。つまずきが記法なのかトレースなのか切り分けたいときは 科目Bがわからない人へ、科目B 全体の進め方は 基本情報技術者 科目B完全対策 が地図になります。
手を動かす練習台としては、過去問AI の 基本情報 アルゴリズムとプログラミング分野の過去問 が使えます（こちらは科目A 相当の選択式で、科目B そのものの形式ではない点だけ意識してください）。各問題ページの AI コパイロットに「この二分探索のコードを lo・hi・mid を列にした表で 1 行ずつトレースして」と頼めば、本記事と同じ追い方を対話でその場で再現できます。
よくある質問
Q. 二分探索はソートされていない配列でも使えますか？ 使えません。二分探索は「真ん中より大きいか小さいか」で範囲を半分に捨てるため、配列が昇順または降順に並んでいることが絶対の前提です。並んでいない配列では捨てた側に答えがある可能性があり、正しく動きません。並べ替えられていない場合は線形探索（先頭から順に調べる）を使います。問題文に「昇順に整列されている」などの条件があるか必ず確認してください。
Q. mid ← (lo + hi) ÷ 2 で小数が出たらどうしますか？ 小数点以下を切り捨てます。擬似言語の ÷ は整数どうしなら商の整数部分を表すため、(1 + 2) ÷ 2 は 1.5 ではなく 1 です。四捨五入や切り上げをすると以降の値がすべてずれ、答えが合わなくなります。「割り切れないときは小さいほうの整数」と覚えておくと安全です。
Q. lo ← mid + 1 の「+1」を書かないとどうなりますか？ 調べる範囲が縮まらず、無限ループになる危険があります。mid の位置はすでに比較済みなので、次に調べる範囲からは mid を外す必要があり、そのために下端なら +1、上端なら -1 します。lo ← mid のように書くと、同じ mid を何度も計算し続けてループが終わらなくなることがあります。
Q. 二分探索は線形探索よりどのくらい速いのですか？ 1 回比べるごとに候補が半分になるため、要素数が大きいほど差が開きます。要素数 n に対し、線形探索は最悪 n 回、二分探索は約 log2(n) 回です。たとえば 1,000 個なら線形探索は最悪 1,000 回、二分探索は約 10 回（2 の 10 乗が 1,024）で済みます。ただし二分探索を使うには配列がソート済みである必要があり、その並べ替えのコストも含めて使い分けます。
まとめ
- 二分探索は 真ん中を見て範囲を半分ずつ捨てる 検索。ソート済み配列が絶対の前提
- 変数は lo（下端）・hi（上端）・mid（中央）・位置。表の列を先に決めて 1 行ずつ追う
- mid ← (lo + hi) ÷ 2 は 小数点以下切り捨て。lo ← mid + 1 / hi ← mid - 1 の ±1 を忘れない
- 見つからないときは lo > hi になって終了し、位置は -1 のまま
- 要素数が大きいほど線形探索より圧倒的に速い（最悪 n 回 → 約 log2(n) 回）
線形探索 → 二分探索とトレースで追えるようになれば、科目Bのアルゴリズム設問は確実に読めるようになります。