二分探索と線形探索の解法：探索範囲の絞り込みとループ終了条件のトレース術

二分探索で最後の一つを見落とすのは、どんなときでしょうか？

両端を含む探索範囲では、leftとrightが同じでも比較します。範囲の更新と終了条件を、一行ずつトレースして確認しましょう。

線形探索と二分探索の決定的な違い：計算量 O(log n) の威力

まず、最も素朴な探索法である「線形探索」と「二分探索」の特徴と計算量を比較して整理しましょう。

探索アルゴリズム	前提条件	最大比較回数（最悪計算量）	平均計算量	特徴と適用場面
線形探索 (Linear Search)	なし（データがバラバラでも可）	n 回（O(n)）	n / 2 回（O(n)）	先頭から順に調べる。ソートされていない配列や少数のデータ向き。
二分探索 (Binary Search)	データが整列済み（昇順または降順）	⌊log₂ n⌋ + 1 回（O(log n)）	O(log n)	中央値との比較で範囲を半減させる。大量データで圧倒的に高速。

例えばデータ数が 1,000,000 件（100万件）ある場合、線形探索では最悪 100万回の比較が必要ですが、二分探索なら最大でもわずか 20 回程度の比較で目的のデータを発見（または不在を確定）できます。

この「半分に捨てる」仕組みこそがアルゴリズムの急所です。

二分探索の基本メカニズムとポインタの動き

二分探索は、探索対象の範囲を指し示す 3 つのポインタ変数（インデックス）を操作して実行します。

現在探索している範囲の「左端の添字」
現在探索している範囲の「右端の添字」
現在探索している範囲の「中央の添字」（計算式: (left + right) ÷ 2 の小数点以下切り捨て）

中央の要素 A[mid] と目的値 target を比較したときの動作ルールは、以下の 3 パターンに完全に集約されます。

比較結果	判定の意味	次に実行するポインタ更新
A[mid] = target	目的の値を発見！探索終了。	現在の添字 mid を返却して終了する。
A[mid] < target	目的値は中央よりも「右側」にある。	left ← mid + 1 （中央以前の左半分をすべて切り捨てる）
A[mid] > target	目的値は中央よりも「左側」にある。	right ← mid - 1 （中央以降の右半分をすべて切り捨てる）

【最重要ポイント：なぜ mid ± 1 なのか？】：A[mid] はすでに目的値と比較済みであり、目的値ではないことが確定しています。そのため、次の探索範囲には mid を含める必要がありません。

もし left ← mid や right ← mid のように更新してしまうと、範囲が狭まらずに同じ比較を永久に繰り返す「無限ループ」のバグを引き起こします。

実戦トレース表の完全作成手順

試験本番で確実に得点するためには、メモ用紙に 1 行ずつ変数の推移を書き出す「トレース表」の作成が必須です。

要素数 8 の昇順配列 A = [3, 8, 12, 21, 28, 34, 45, 59]（添字は 0 から 7）を対象に、実際のトレース手順を見てみましょう。

ケース①：目的値が存在する場合（target = 34 を探索）

Step	left	right	計算 mid	中央値 A[mid]	比較判定 (target vs A[mid])	次の更新処理
初期値	0	7	-	-	-	探索開始 (0 ≦ 7 なのでループ突入)
1回目	0	7	(0+7)÷2 = 3	A[3] = 21	34 > 21 (大)	left ← mid + 1 = 4 に更新
2回目	4	7	(4+7)÷2 = 5	A[5] = 34	34 = 34 (一致！)	探索成功！添字 5 を返却して終了

わずか 2 回のループで正確に添字 5 を特定できました。

ケース②：目的値が存在しない場合（target = 25 を探索）

配列中に存在しない値を探す場合、「どのような条件で探索失敗と判断してループを抜けるか」が頻出の出題ポイントです。

Step	left	right	計算 mid	中央値 A[mid]	比較判定 (target vs A[mid])	次の更新処理
初期値	0	7	-	-	-	探索開始
1回目	0	7	3	A[3] = 21	25 > 21 (大)	left ← 3 + 1 = 4
2回目	4	7	(4+7)÷2 = 5	A[5] = 34	25 < 34 (小)	right ← 5 - 1 = 4
3回目	4	4	(4+4)÷2 = 4	A[4] = 28	25 < 28 (小)	right ← 4 - 1 = 3
判定	4	3	-	-	left (4) > right (3)	逆転成立！ループ終了（未発見：-1 を返却）

3回目のループで right が 3 に更新された結果、「left (4) > right (3)」となり、探索範囲が消失（左右が逆転）しました。この逆転こそが「配列内に目的の値が存在しなかった」証拠です。

設問者が仕掛ける「3大境界値トラップ」

二分探索の設問で出題者が意図的に仕掛けるひっかけパターンは、以下の 3 つに集中しています。

添字の開始番号（0始まり vs 1始まり）：問題文冒頭の添字定義を必ず確認すること。0始まりなら初期値は right ← n - 1、1始まりなら right ← n となる。これを間違えると末尾要素が探索対象から漏れる。
このコードは両端を含む閉区間[left,right]を使います。left＝rightなら最後の1要素が残るため、継続条件はleft≦rightです。右端を含まない半開区間の実装では、終了条件や更新式が異なります。
奇数・偶数の切り捨て処理：(left + right) ÷ 2 の除算で小数点以下が切り捨てられるのか、四捨五入なのか。通常は整数除算（div）で切り捨てとなり、要素が偶数個の場合は前半の中央が選ばれる。

実戦演習：二分探索の擬似言語穴埋め問題

以下のプログラムは、昇順に整列された整数型の配列 A から値 target を探索し、見つかった場合はその添字を、見つからなかった場合は -1 を返す関数です。空欄に入る適切な式を考えてみましょう。

text

○整数型: BinarySearch(整数型の配列: A, 整数型: n, 整数型: target)
  整数型: left, right, mid
  left ← 0
  right ← n - 1

  while ( 【   a   】 )
    mid ← (left + right) div 2
    if (A[mid] = target) then
      return mid
    elseif (A[mid] < target) then
      【   b   】
    else
      right ← mid - 1
    endif
  endwhile

  return -1

【空欄 a の選択肢】

left < right
left ≦ right
left ≠ right
mid ≦ right

【空欄 b の選択肢】

left ← mid
left ← mid + 1
right ← mid
right ← mid + 1

解説と解答

正解：空欄 a ＝イ（left ≦ right）、空欄 b ＝イ（left ← mid + 1）

探索範囲に要素が 1 つだけ残った場合（left = right のとき）も、その要素が target と一致するか検証する必要があります。そのため、等号を含んだ left ≦ right が正解です。
ア（left < right）では最後の1要素が検証されずに -1 で返却されてしまいます。
A[mid] < target は「目的値が現在の中央値よりも大きい」ことを意味するため、目的値は中央より右側に存在します。中央 mid はすでに不一致と確定しているため、次の探索範囲の左端は left ← mid + 1 と更新します。

空配列、重複、計算量の前提

添字0始まりのこの実装では、n＝0ならright＝−1となり、比較せず−1を返します。n＝1でも一致・不一致を判定できることを確認します。

同じ値が複数ある場合、このコードは一致したどれか一つを返します。最初や最後の添字が必要なら、一致後も範囲を狭める別の処理が必要です。

昇順配列の二分探索で、n≧1の最悪比較回数はfloor(log₂n)＋1です。線形探索の成功時の平均比較回数は、各位置が同じ確率なら(n＋1)/2。見つからない場合はn回です。

固定幅整数ではleft＋rightがオーバーフローする可能性があります。中央はleft＋(right−left) div 2の形で計算できます。

まとめ：二分探索を解くチェックリスト

二分探索問題に遭遇したら、以下の 4 ステップを機械的にチェックしましょう。

配列がソートされているか確認する（昇順か降順か）。
添字の開始値（0始まりか1始まりか）を見て、初期の left と right を設定する。
ループ条件が left ≦ right になっているか確認する。
left、right、mid、A[mid]の4列を用意し、指定したデータでループ終了まで追う。必要な行数は配列の大きさで変わる。

出典と仕様を確認する

IPA：FEシラバス Ver.9.2

IPA：試験で使用する用語・プログラム言語 Ver.5.1

Princeton：二分探索の実装