c++ - 二分搜索在什么时候变得比顺序搜索更有效？

Question

我最近学习了很多有关算法的知识，二进制搜索因其在大量已排序 数据中查找项目的效率而广受赞誉。但是，如果数据一开始就没有排序怎么办？二分搜索在什么时候提供了顺序搜索的效率提升，二分搜索必须首先对给定的数组进行排序然后搜索。我很想知道二进制搜索在哪些点上超过顺序搜索，如果有人在我之前测试过这个，我很想看到一些结果。

给定一个包含 14 个元素的数组 foo[BUFF]

1 3 6 3 1 87 56 -2 4 61 4 9 81 7

我假设顺序排序会更有效地找到给定的数字，比方说... 3，因为二分搜索需要先对数组排序然后搜索数字 3。但是:

给定一个包含一千个元素的数组 bar[BUFF]

1 2 4 9 -2 3 8 9 4 12 4 56 //continued

如果我没记错的话，理论上调用排序然后二分查找应该更有效。

Answer 1

在信息未知的未排序数组中，您将不得不进行线性时间搜索。

线性时间搜索对每个元素检查一次，所以它的复杂度是O(n)。将其与排序进行比较。排序算法必须多次检查每个元素，复杂度为 O(n * log n)。因此，即使对其进行排序也比顺序搜索慢。即使二进制搜索是 O(log n)，但当您只有任意排序的数据时，它也毫无用处。

如果您要多次搜索内容，请考虑先进行排序，因为从长远来看，这会提高您的效率。