我正在努力了解二进制搜索算法的速度。我知道它需要对排序数组进行操作。但是，如果数组未排序并执行排序。排序不是二进制搜索的一部分，因此它的性能会更慢吗？
我很困惑，因为我认为如果数据没有排序，使用这种算法的机会很小。如果我的代码需要对它进行排序，那么为什么它不计入搜索算法呢。
对不起，如果我感到困惑，谢谢你的帮助。
你不能只是指着一个算法说：它有O(n^2)的复杂性！
这是人们通常说的，当然。但这只是简写。他们在省略一些东西；假设听众/读者会做出假设。
您需要充分描述精确的算法、应用它的条件，以及n和任何其他变量的精确定义。
然后，你可以回答这个问题。这里的问题是"二进制搜索的性能"的定义不清楚。如果你认为它的意思是X，而你的朋友认为它的含义是Y，然后你就答案争论不休，那么你实际上根本没有进行建设性的辩论。你只是在向风车倾斜；真正的问题是，你们两个都没有意识到问题在于交流基础知识。
考虑到这里有一些混乱，我将给你3个不同的、或多或少同样合理的、更充实的定义，以及每个这样的定义的实际答案。提示，对其中一个来说，"二进制搜索"不是最快的算法！
给定[1]一个已经排序的列表和[2]一个值，给我写一个算法来确定这个值是否在列表中。
最好的答案是：二进制排序算法，其复杂度为O(log n)。
给定[1]一个未排序的列表和[2]一个值，请给我写一个算法，确定该值是否在列表中。
最好的答案是：只需遍历列表。它的复杂度是O(n)，二进制排序根本不是这个答案的一部分。
给定[1]一个未排序的列表和[2]一个测试列表，其中每个单独的测试都由一个值定义，但它们都使用相同的输入未排序列表，编写一个算法，用于每个测试，确定该测试的值是否在列表中，然后给我分摊的复杂性(基本上，整个事情的复杂性，除以我们运行的测试数量)。
那么最好的答案是：首先对列表进行排序，花费O(n log n)的时间进行排序，但我们可以将其分摊到测试用例计数中，然后对每个单独的测试使用二进制搜索，为每个测试添加O(log n)的复杂度。如果我们将n称为输入列表的大小，将t称为我们拥有的测试数量，则得到：
O( (n log n)/t + O(log n) )
这是问题的实际答案，尽管看起来很复杂。但是，如果t很大，甚至被认为是无限大的，或者我们在这个问题上再加一个附加条件：
[1]中的列表提前提供给您，在合理的时间和内存限制内，您可以预处理这些数据，而无需在测试用例中摊销这些成本
那么这归结为O(log n)，因为t的大值使(n log n) / t因子接近零。
在与你的好友交流时，考虑到我们在整篇科学论文中都没有交谈，人们可能会说："；二进制排序算法的算法复杂度是O(logn)〃；，即使这省略了整个故事的一大块。
根据第二种情况解释问题(输入未排序，输入包括要搜索的列表和值，没有多测试子句)。有人说"二进制搜索是O(logn)"，这不是第一个就是第三个。你们都是对的。
注意：第三个定义似乎异常复杂。然而，它符合常见场景。例如，"我们编制了一份居住在城里的人的名单和他们的电话号码，我们想把它们印在一本巨书中，目的是让这本书的收件人查找电话号码。我们预计，在一次印刷的生命周期内，该镇的10万名公民平均将进行约50次查找，这一列表的总查找量为500万次。这就给了你t=500万，n=20万(假设有20万人住在这里，其中一半有电话簿)。插入这些号码并对电话簿进行排序与以任意、未排序的顺序发布电话簿相比，以压倒性优势获胜。即使，是的，你开始"减少"分拣工作，直到一些人在打印这本书之前迅速查找了几个电话号码来弥补你的分拣工作，你才能够弥补这一损失。
是如果
- 数据未排序
- 您只需要搜索一个元素
。。。然后您必须首先对数据进行排序以使用二进制搜索，这将总共花费O(n log n+log n)=O(n logn)时间。
但一旦对数据进行了排序，您就可以根据需要对该数据进行多次二进制搜索。你不必每次都重新排序。