在未排序的数组中，为什么我更喜欢二进制搜索而不是线性搜索？

Question

我一直在学习Coursera上的DSA课程，本周介绍了搜索算法。而二进制搜索（O（logn））的复杂度优于线性搜索（O（n））。但是，考虑到首先对数组进行排序需要nlogn工作，为什么我要在未排序的数组中使用它呢。

如果二进制搜索只在数组已经排序的情况下使用，那么为什么这两种算法经常比较，因为显然它们有不同的用例。

Answer 1

Willem Van Onsem的答案很好地描述了将对同一个数组进行许多查询的情况，因此值得先花O（n log n）时间对数组进行排序。我的答案没有直接解决“未排序的数组”，但有一个常见的误解，即数组要么未排序，要么已排序，我认为值得解决这个误解，以防对任何读者有所帮助。

说清楚一点，我不认为你有这种特殊的误解；但我确实认为一些有这种误解的人会读到你的问题及其答案。

“排序”这个词有点误导。由于“排序”是一个过去式动词，它听起来像是一个排序算法被用来把数据排序。但是计算机科学家使用“排序”这个词的方式，它只是意味着数组是有序的，而不是暗示它以前不是有序的。

因此，当我们说二进制搜索只能用于“排序的数组”时，这并不意味着需要O（n log n）时间才能使数组“排序”。大量数据自然有序，无需进行任何排序工作。几个例子：

• 假设我有一个未排序的数字数组，我想构建一个前缀和数组，它包含从原始数组开始的累积和。如果原始数组中没有负数，那么累积和自然将按升序排列
• 假设我有一个包含一些特殊元素的序列，我想执行查询，在给定索引的情况下，查询会找到该索引之后的第一个特殊元素。这将有助于按照特殊元素出现的顺序列出索引；找到这些指数的自然方法是按升序找到它们
• 假设我想要一个第一个素数数组，或者所有小于或等于n的素数数组。几乎任何解决这两个问题的算法都会按升序生成素数

因此，在许多情况下，我们可以应用二进制搜索，而无需花费O（n log n）时间来排序需要搜索的序列。

Answer 2

我是否会在未排序的数组中使用它，因为首先对数组进行排序需要O（n log n）个工作。

通常情况下，一个人会对同一数据结构执行多个查询。事实上，以数据库为例。一个人获取具有给定主键的记录的频率高于添加记录的频率，这是有道理的。这是有道理的，因为如果查询的数量低于插入的数量，那么我们插入的数据永远不会被检索到，因此这些数据是“无用的”。

此外，排序元素列表或构建元素二叉树确实需要O（n log n）。但是更新二叉搜索树，例如AVL树[维基]需要O（log n）。因此，如果您通过添加一个元素、删除一个元素、更新一个元素等方式略微更改元素集合，则需要O（log n）来更改数据结构，并且您需要保持O（log n）查找。

对未排序的数据使用线性搜索，确实会胜过对少量查询的排序和二分搜索。从查询数量变大的那一刻起，线性搜索算法就会被二分搜索算法超越。