algorithm - 配列がソートされていない場合、どの検索手法を使用できますか？

Question

二分探索はO（log n）で探索を行います。ただし、配列がソートされている場合にのみ使用できます。

配列がソートされていない場合、どの検索手法が最適ですか？

Answer 1

数回の検索のみを行う場合は、基本的な線形検索が最善の方法です。

頻繁に検索する場合は、通常、並べ替えてから、バイナリ検索を使用することをお勧めします（または、コンテンツの分布がかなり予測可能な場合は、補間検索を使用します）。

Answer 2

データがソートされていない場合は、ハッシュテーブルを使用してO（1）時間でデータにアクセスできます。

Answer 3

線形検索を行うことができます。しかし、線形検索の問題は、パフォーマンスの問題があることです。これには多くの時間がかかります。したがって、可能であれば配列を並べ替えてから、バイナリ検索を使用することをお勧めします。さらに優れたレイテンシーが必要な場合は、一般的なバイナリ検索のビット最適化バージョンである補間検索を試してください。