基本情報技術者 一問一答｜A 第53問

解説

二分探索は、整列済みの配列に対して中央の要素と目的の値を比較し、大小関係に応じて探索範囲を毎回半分に絞り込む手法である。要素数nに対する最大比較回数はおよそ⌈log₂n⌉回（厳密には⌊log₂n⌋＋1回）であり、計算量はO(log n)となる。例えばn＝1000なら2¹⁰＝1024＞1000より最大10回程度、n＝100万でも約20回で探索が完了する。n回は先頭から順に調べる線形探索の最悪値、n/2回は線形探索の平均比較回数、n²回は単純ソートなどに現れるオーダーであり、いずれも二分探索の比較回数ではない。基本情報技術者試験では具体的なnに対する最大比較回数の計算、線形探索との比較回数の差、整列済みであることが前提条件である点が頻出ポイントである。