arrays - 未排序数组的二分查找时间复杂度

Question

我被两个时间复杂性所困扰。使用排序数组进行二进制搜索是 O(logN)。所以要搜索一个未排序的数组，我们必须首先对其进行排序，使其变为 O(NlogN)。因此，我们可以执行二进制搜索，其复杂度为 O(N)，但我读过它可能是 O(NlogN)。哪个是对的？

Answer 1

二进制搜索适用于“排序”列表。复杂度为 O(logn)。

二进制搜索不适用于“未排序”列表。对于这些列表，只需从第一个元素开始进行直接搜索；这给出了 O(n) 的复杂度。如果您要使用 MergeSort 或任何其他 O(nlogn) 算法对数组进行排序，那么复杂度将为 O(nlogn)。

O(logn) < O(n) < O(nlogn)

Answer 2

你的问题的答案就在你的问题本身。

您首先对列表进行排序。如果您使用快速排序或合并排序对列表进行排序，复杂度将变为o(n*log n). 第 1 部分结束。

执行二进制搜索的第二部分是在“排序列表”上完成的。二分查找的复杂度为o(log n). 因此最终程序的复杂性仍然存在o(n*log n)。

但是，如果您希望计算数组的中位数，则不必对列表进行排序。线性或顺序搜索的简单应用程序可以帮助您。

Answer 3

线性搜索的时间复杂度是O(n)，二分搜索的时间复杂度是O(log n)(log base-2)。如果我们有一个未排序的数组并且想要对此使用二进制搜索，我们必须首先对数组进行排序。在这里我们必须花时间O(n logn)对数组进行排序，然后花时间搜索元素。