我一直在Coursera上学习DSA课程，本周已经介绍了搜索算法。而二叉搜索(O(logn((的复杂性优于线性搜索(O(n((。但是，鉴于首先对数组进行排序需要 nlogn 工作，我为什么要在未排序的数组中使用它。
如果二叉搜索只在数组已经排序的情况下使用，那么为什么这两种算法经常进行比较，因为它们显然有不同的用例。
我会在未排序的数组中使用它吗，因为首先对数组进行排序需要 O(nlog n( 工作。
通常，对同一数据结构执行多个查询。事实上，例如在数据库中查找。与添加记录相比，人们更频繁地获取具有给定主键的记录是有道理的。这是有道理的，因为如果查询数量低于插入次数，那么我们插入的数据永远不会被检索，因此这些是"无用的"。
此外，对元素列表进行排序或构建元素的二叉树确实需要O(n log n(。但是更新二叉搜索树，例如AVL树[wiki]需要O(log n(。因此，如果您稍微更改元素集合，请通过添加一个元素，删除一个元素，更新一个元素等。它需要O(log n( 来更改数据结构，并且您继续维护O(log n(查找。
对未排序的数据使用线性搜索，确实会优于少量查询的排序和二叉搜索。从查询数量变得大的那一刻起，线性搜索算法的性能就会被二叉搜索算法所超越。
Willem Van Onsem 的回答很好地描述了在同一数组上进行许多查询的情况，因此值得先花 O(n log n( 时间对数组进行排序。我的回答没有直接解决"未排序的数组"，但有一个常见的误解，即数组要么是未排序的，要么已经被排序，我认为值得解决这种误解，以防它对任何读者有所帮助。
需要明确的是，我不认为你有这种特殊的误解;但我确实认为一些有这种误解的人会阅读你的问题及其答案。
"排序">这个词有点误导。由于"sorted"是一个过去时态动词，因此听起来像是使用排序算法来整理数据。但是计算机科学家使用"排序"这个词的方式，它只是意味着数组是有序的，并不意味着它以前没有顺序。
因此，当我们说二叉搜索只能在"排序数组"上使用时，这并不意味着需要 O(n log n( 时间来使数组"排序"。大量数据自然井然有序，无需做任何工作即可对其进行排序。举几个例子：
- 假设我有一个未排序的数字数组，我想构建一个前缀 sum 数组，其中包含从原始数组开头开始的累积总和。如果原始数组中没有负数，则累积总和自然会按升序排列。
- 假设我有一个包含一些特殊元素的序列，并且我想执行查询，其中给定一个索引，查询在该索引之后找到第一个特殊元素。按照特殊元素出现的顺序列出索引会有所帮助;查找这些索引的自然方法是按升序找到它们。
- 假设我想要一个前
n个素数的数组，或者所有小于或等于n的素数。几乎任何解决任一问题的算法都会按升序生成素数。
因此，在许多情况下，我们可以应用二叉搜索，而不必花费O(n log n(时间来对需要搜索的序列进行排序。