教科書で学ぶ探索と整列のアルゴリズム
定義線形探索法は、データの先頭から順に 1 つずつ 目的の値と比べ、一致した時点で終える探索法である。
解説データが並べ替えられていなくても、そのまま使える。比較回数は目的の値の位置で決まり、末尾にある場合や見つからない場合は全件と比べることになる。平均すると、およそ件数の半分の回数の比較が要る。
たとえ背表紙の並びがばらばらの本棚で、目当ての本を左端から 1 冊ずつ確かめていくようなもの。
記憶フック「線形」は一本の線。線をなぞるように、端から一方向へ進む。