二分探索とは
整列済みのデータの中央と比べて、探す範囲を毎回半分に絞る探索法。計算量は O(log n) です。
解説
二分探索は、昇順に並んだ配列の中央の要素と探す値を比べ、探す値が小さければ前半、大きければ後半へ範囲を絞って繰り返す方法です。1回の比較で候補が半分になるので、n 件のデータでも比較は高々 log₂n 回程度で済みます（100万件でも約20回）。ただし、データがあらかじめ整列されていることが前提で、整列されていなければ使えません。先頭から順に調べる線形探索は平均 n/2 回の比較が必要です。
試験での出方
最大比較回数の計算や、探索の途中経過を追わせる問題が出ます。「整列済みが前提」「計算量 O(log n)」を押さえます。
あわせて読みたい用語
この用語が解説に出てくる問題
- 平成28年度 春期 問510個の節（ノード）から成る次の2分木の各節に，1から10までの値を一意に対応するように割り振ったとき，節a，bの値の…
- 平成26年度 春期 問19ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで，複数のデータが同じハッシュ値になることはないものとする。
- 令和3年度 秋期 問9属性が n 個ある関係の異なる射影は幾つあるか。ここで，射影の個数には，元の関係と同じ結果となる射影，及び属性を全く含…
- 平成31年度 春期 問16関係データベースにおいて，タプル数nの表二つに対する結合操作を，入れ子ループ法によって実行する場合の計算量はどれか。
- 平成24年度 春期 問18関係データベースにおいて，タプル数nの表二つに対する結合操作を入れ子ループ法によって実行する場合の計算量は幾らか。
この用語がよく出る分野：アルゴリズムの要点と過去問一覧