如何获得用于二进制搜索操作的排序数组？
How to obtain a sorted array for binary search operation?
我最近学习了二分查找....它的 O(log n) 的时间复杂度给我留下了深刻的印象，但我怀疑要获得排序的数组我必须应用排序操作即最小 O(nlogn) 复杂度，这是相当多的。
如果您有一个未排序（或不能保证排序）的列表，线性搜索是可行的方法。线性搜索是 O(n)，而排序是 O(nlog n)，后者更糟。即使检查列表是否已排序也是 O(n).
如果只想搜索一次列表，最好使用线性搜索。如果您要搜索多次，您可能会受益于首先对列表进行排序。为了找出最适合您的具体情况的方法，您必须分析问题。
想法是对列表进行一次排序，并保留结果。随后的搜索是 O(log n)。因此，您在许多搜索中的复杂度为 (n log n) + S*log(n)，其中 S 是您将进行的搜索次数。如果您不对数组进行排序，那么您的多次搜索将花费 O(S*n).
我最近学习了二分查找....它的 O(log n) 的时间复杂度给我留下了深刻的印象，但我怀疑要获得排序的数组我必须应用排序操作即最小 O(nlogn) 复杂度，这是相当多的。
如果您有一个未排序（或不能保证排序）的列表，线性搜索是可行的方法。线性搜索是 O(n)，而排序是 O(nlog n)，后者更糟。即使检查列表是否已排序也是 O(n).
如果只想搜索一次列表，最好使用线性搜索。如果您要搜索多次，您可能会受益于首先对列表进行排序。为了找出最适合您的具体情况的方法，您必须分析问题。
想法是对列表进行一次排序，并保留结果。随后的搜索是 O(log n)。因此，您在许多搜索中的复杂度为 (n log n) + S*log(n)，其中 S 是您将进行的搜索次数。如果您不对数组进行排序，那么您的多次搜索将花费 O(S*n).