【科目B対策】2分探索法を擬似プログラミング言語で理解する

― 「半分ずつ捨てる」高速な探索アルゴリズム ―

はじめに

基本情報技術者試験・科目Bでは、探索アルゴリズムとして次の3つが扱われます。

  • 線形探索法
  • ハッシュ法
  • 2分探索法

この記事では、その中でも「なぜ速いのか」「なぜ条件があるのか」が問われやすい

2分探索法（にぶんたんさくほう）について解説します。

2分探索法とは？

一言でいうと

2分探索法とは、探索範囲を半分ずつに絞りながら目的のデータを探すアルゴリズムです。

線形探索のように先頭から1つずつ確認する方法ではありません。

2分探索法の重要な特徴（試験に出る）

2分探索法には、必ず押さえておくべき特徴が2つあります。

特徴①

データは、あらかじめ昇順（または降順）に並んでいる必要がある

特徴②

探索範囲を、2つに分けながら探索する

👉 この2つは、

そのまま選択肢として出題されるレベルの重要事項です。

なぜ「並んでいる必要」があるのか？

2分探索法では、

  • 中央の値と
  • 探したい値

を比較し、

  • 小さい → 左半分に存在する
  • 大きい → 右半分に存在する

と判断します。

👉 大小関係が使えるのは、並んでいるからです。

具体例で考える

次のような配列を考えます。

A = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

ここから 「6」 を探します。

手順①：中央の要素を見る

  • 先頭の要素番号：1
  • 末尾の要素番号：9
(1 + 9) ÷ 2 = 5

中央は 要素番号5（値は5） です。

手順②：比較する

  • 探索対象：6
  • 中央の値：5
6 > 5

👉 左半分には存在しない

👉 右半分（6〜9）に絞る

手順③：同じことを繰り返す

探索範囲は次のようになります。

A = [ 6, 7, 8, 9 ]

再び中央を求めます。

(6 + 9) ÷ 2 = 7.5 → 7

中央の値は 7。

6 < 7

👉 今度は 左半分 に絞る

手順④：発見

残った配列は

[ 6 ]

👉 目的のデータを発見

擬似プログラミング言語での表現

前提

  • 配列 A は昇順に整列済み
  • 探索対象を KEY とする

擬似コード例（基本形）

LEFT ← 1
RIGHT ← N
FOUND ← false

while LEFT ≤ RIGHT and FOUND = false
  MID ← (LEFT + RIGHT) ÷ 2

  if A[MID] = KEY then
    FOUND ← true
  elseif A[MID] < KEY then
    LEFT ← MID + 1
  else
    RIGHT ← MID - 1
  endif
endwhile

擬似コードの読み取りポイント（重要）

① 中央の求め方

MID ← (LEFT + RIGHT) ÷ 2

👉 2分探索法の核心

② 探索範囲の更新

  • LEFT ← MID + 1
  • RIGHT ← MID – 1

👉 中央はもう調べたので除外する

③ ループが止まる条件

  • 見つかった
  • 探索範囲がなくなった

👉 無限ループ対策としてよく出題されます。

探索回数の少なさが最大の強み

2分探索法では、

  • データ数が増えても
  • 毎回、探索範囲が 半分 になります。

例：

  • 8個 → 4個 → 2個 → 1個

👉 非常に効率が良い探索アルゴリズムです。

線形探索法との違い（比較）

項目線形探索法2分探索法
並び順不要必要
探索方法1つずつ半分ずつ
速度遅い速い
理解しやすさ高いやや難しい

科目Bでの注意点

① 「並んでいない配列」で使えない

選択肢で、

  • 「データが整列されていなくてもよい」

と書かれていたら 誤り です。

② 中央要素の扱い

  • 切り捨て
  • 切り上げ

👉 試験では

どちらでも成り立つように作られています。

まとめ

  • 2分探索法は「半分ずつ捨てる」探索アルゴリズム
  • データは 必ず整列済み
  • 中央の値との比較がすべて
  • 科目Bでは条件・流れ・止まる理由 を読めることが重要
訪問数 7 回, 今日の訪問数 7回

アルゴリズム,基本情報技術者,情報処理試験

Posted by hidepon