
線形探索と二分探索
用語の意味
線形探索は先頭から順に値を調べる方法です。二分探索は整列済みのデータで中央の値と目標値を比べ、候補を半分ずつに絞ります。
使いどころと問題の見方
昇順の配列で中央の値が目標より大きければ、中央より左だけを残します。見つからない場合に備え、候補区間が空になったら終了します。配列での最悪時の比較回数は、線形探索が要素数に比例するのに対し、二分探索は要素数の対数に比例します。
確認問題【オリジナル】
昇順の配列[2, 5, 9, 13, 21]から5を二分探索します。最初に9と比較した後、候補として残す値はどれですか。
ア.2と5
イ.9と13
ウ.13と21
エ.5と13
正解と理由
正解はアです。9は5より大きいため、9より左の2と5だけが候補に残ります。