探索アルゴリズムの中でも最も単純なものが線形探索です。線形探索は、探索するデータの並びの中からキーとなる値を、先頭から最後まで単純に探索していくものです。別名逐次探索とも言われています。

二分探索アルゴリズムは、前もって小さい順、または大きい順に整列しているデータに対し、探索範囲の中央にある値を調べ、その値と探したい値の大小によって右左どちらか一方に探索範囲を絞り込む。これを繰り返しながら、目的のものを探し出します。

６cmから２５cmの高さを持つ、２０本の棒の中から「高さ１６cm」の値を持つ棒を探す。探索のキーは１６cm、探索範囲は1から20まで。２０本の棒は、小さい順で並んでいる。まず真中の棒の高さを調べる。10番の棒の高さは１５cmなので目的の棒は10番より右側にある。探索範囲を11から20に絞る。その真中の１５番の棒の値は２０cm。これにより目的の棒は11番から１４番の間にあることが分かる。探索範囲を11番から１４番に絞りこみ、真中の値を調べると、１２番の棒の値は１７cmなので、目的とする棒は11番であることが分かる。