バイナリ検索操作のための並べ替えられた配列を取得する方法？

Question

私は最近バイナリ検索を学びました....私はO（log n）の時間の複雑さに非常に感銘を受けましたが、ソートされた配列を得るためにはソートされた演算、すなわち最小O （nlogn）の複雑さはかなり大きいです。

Answer 1

ソートされていない（ソートされていることが保証されていない）リストがある場合は、リニア検索が必要です。線形探索はO（n）であり、ソートはO（nlog n）であり、これは悪化する。リストがソートされているかどうかをチェックすることもO（n）です。

リストを一度しか検索しない場合は、線形検索のほうがよいでしょう。何回か検索する場合は、まずリストをソートすると効果があります。特定のケースに最適なものを見つけるには、問題を分析する必要があります。

Answer 2

アイデアは、リストを一度ソートして結果を保持することです。その後の検索はO（log n）です。したがって、多くの検索での複雑さは(n log n) + S*log(n)です。ここでは、Sが検索の数です。配列をソートしないと、複数の検索のコストはO(S*n)になります。