我被两个时间复杂性困住了。使用排序数组进行二分搜索是 O(logN)。所以要搜索一个未排序的数组，我们必须先对它进行排序，使其变为 O(NlogN)。那么我们可以执行二分搜索，它的复杂度为 O(N)，但我已经读过它可能是 O(NlogN)。哪个是正确的？
最佳答案
二分搜索用于“排序”列表。复杂度是 O(logn)。
二分搜索不适用于“未排序”列表。对于这些列表，只需从第一个元素开始直接搜索；这给出了 O(n) 的复杂度。如果您要使用 MergeSort 或任何其他 O(nlogn) 算法对数组进行排序，那么复杂度将为 O(nlogn)。
O(logn) < O(n) < O(nlogn)
关于arrays - 未排序数组二分查找的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15911943/