2

我最近一直在学习很多关于算法的知识，二进制搜索因其在大量排序数据中查找项目的效率而受到赞誉。但是，如果数据一开始就没有排序怎么办？二进制搜索在什么时候可以提高顺序搜索的效率，二进制搜索必须先对给定的数组进行排序，然后再进行搜索。如果有人在我希望看到一些结果之前测试过这个，我很想看看二进制搜索在什么时候通过顺序搜索。

给定一个包含 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

如果我没记错的话，理论上调用排序然后二进制搜索应该更有效。

4

2 回答 2

12

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

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

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

于 2012-12-08T10:36:40.263 回答
4

如果您需要进行多次搜索，那么在搜索之前进行排序只会更快。如果您只需要找到一个元素，那么排序会更慢，因为无论如何排序都必须在某个时候检查每个元素。

如果您要进行多次搜索，可能值得先排序，但收支平衡点（在线性搜索和预排序 + 二分搜索之间）将取决于所需的搜索次数、元素数量、排序算法使用，以及正在排序的数据。

于 2012-12-08T10:35:51.907 回答