二进制搜索在什么时候比顺序搜索更有效？

Question

我最近一直在学习很多关于算法的知识,并且搜索到的二进制文件因其在大量排序数据中查找项目的效率而受到欢迎.但是,如果数据没有排序开始怎么办？在什么点上二进制搜索提供了对顺序搜索的效率提升,二进制搜索必须首先对给定数组进行排序然后搜索.我有兴趣看看二进制搜索在顺序搜索中经过什么点,如果有人在我希望看到一些结果之前测试了这一点.

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

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

我假设顺序排序会更有效地找到给定的数字,让我们说... 3,因为二进制搜索需要先对数组进行排序然后搜索数字3.但是:

给定一个数组栏[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)只要你有任意排序的数据,它就没用了.

如果您要多次搜索内容,请先考虑排序,因为从长远来看它会提高效率.