binary-search - 逐次探索が二分探索よりも優れているのはいつですか?

Question

そんなこと知ってる：

線形検索は、一度に 1 項目ずつジャンプせずにリストを調べます。複雑さの点では、これは O(n) 検索です。リストの検索にかかる時間は、リストと同じ割合で大きくなります。

二分探索とは、並べ替えられたリストの中央から開始し、それが探している値よりも大きいか小さいかを調べることです。これにより、値がリストの前半または後半にあるかどうかが決まります。サブリストの途中までジャンプして、もう一度比較するなど。

二分探索よりも逐次・線形探索の方が効率的になる場合はありますか？

Answer 1

はい、たとえば、探しているアイテムがたまたまシーケンシャル検索で最初に表示されたアイテムの 1 つだった場合などです。