2分探索｜まん中と比べて、探す範囲を半分にする【基本情報技術者試験 科目B】

現行FE シラバス Ver9.2 準拠擬似言語の記述形式は2022年から変更なし最終更新 2026-10-11

2分探索は、小さい順に並んだ配列から目当ての値を探すやり方です。まん中の1つと比べるたびに、探す範囲が半分になります。

期間限定クーポンPR｜Udemy の講座科目B オリジナル模試 3回分・60問42%OFF 1,500円2,600円中身を見る ›

2分探索とは ── まん中と比べて、半分を捨てる

6個の値が小さい順に並んだ配列から、47 が何番目にあるかを探します。見るのは毎回、探す範囲のまん中の1つだけです。

毎回やることは同じです。

1回比べるたびに範囲が半分になるので、配列が大きくても比べる回数は少なくて済みます。1000個あっても、1000 → 500 → 250 → … と半分にするのを10回ほどくり返せば、残りは1個です。前から1つずつ比べていく線形探索だと、目当ての値が最後にあれば1000回かかります。

並んでいることが前提

まん中の1つを見ただけで半分を捨てられるのは、配列が小さい順に並んでいるからです。並んでいない配列で同じことをすると、こうなります。

小さい順に並んでいることを昇順といいます。この探し方を使うプログラムは、配列が昇順に並んでいることを前提にしています。

プログラムを、上から読む

ここまでの手順を関数にしたものです。配列 data と探す値 target を受け取り、見つかればその要素番号（何番目か）を、見つからなければ －1 を返します。47 を探した図の「左端」「右端」「まん中」が、変数 low・high・middle です。

○整数型: nibunTansaku(整数型の配列: data, 整数型: target)
  整数型: low, high, middle
  low ← 1
  high ← dataの要素数
  while (low ≦ high)
    middle ← (low ＋ high) ÷ 2 の商
    if (data[middle] ＜ target)
      low ← middle ＋ 1
    elseif (data[middle] ＞ target)
      high ← middle － 1
    else
      return middle
    endif
  endwhile
  return －1

当サイトで作った例です。

data が {11, 23, 35, 47, 59, 62}、target が 47 なら、47 を探した図のとおり、まん中を3回見て 4 を返します。

終わり方は2つ ── 見つかったとき、範囲が空になったとき

1つ目は、47 を探した図の3回目です。middle が 4 で、data[4] が 47 と同じなので、return middle で 4 を返します。2つ目を、同じ配列で入っていない値 20 を探して確かめます。

左端が右端より右に来たら、範囲には1つも残っていません。だから while を抜けて、－1 を返します。

くり返しのたびに、middle 番は必ず範囲から外れます。範囲は毎回1つ以上せまくなるので、見つからない場合もいつかは空になり、くり返しは終わります。

次に読む