教科書で学ぶ探索と整列のアルゴリズム
定義2分探索法は、値の小さい順 (昇順) か大きい順 (降順) に並んだ整列済みのデータで、探索範囲の 中央 の値と比べて目的の値がある側へ範囲を半分ずつ絞る探索法である。
解説昇順の場合、目的の値が中央の値より小さければ前半、大きければ後半だけを残し、一致するか範囲がなくなるまで繰り返す。1 回の比較で候補が約半分になるので、件数が 2 倍になっても比較は 1 回ほどしか増えない。ただし比較回数は探す値の位置でも変わり、先頭近くの値なら線形探索法の方が少ない回数で見つかることもある。
たとえ番号順に重ねた受付票の束から真ん中の 1 枚を抜き、目当ての番号が前か後ろかを決めて、残った半分でまた真ん中を見るようなもの。
記憶フック「2分」は 2 つに分けること。英語の binary search の binary も「2 つの」を表す。