是否存在Ω(logN)复杂度的算法在未排序数组中查找最接近X的元素？

首先明确结论：在未排序数组中，你必须遍历所有N个元素才能找到最接近X的元素，不存在能跳过部分元素的O(logN)算法。

为什么会和教材表述产生矛盾？ #

你看到的决策树下界Ω(logN)，是针对已排序数组的场景：

• 当数组有序时，我们可以用二分查找的变种快速定位X的大致位置，再比较相邻几个元素就能确定最接近X的值，这个过程时间复杂度为O(logN)，对应的决策树模型也符合Ω(logN)的下界——因为每次比较都能基于有序性排除一半左右的元素。

未排序数组的本质限制 #

未排序数组没有任何顺序信息可利用，每个元素与X的距离都是独立的：

• 你无法通过某个元素和X的大小关系，推断其他元素与X的距离。比如看到A[i]和X的差是2，完全没法确定数组里有没有差更小的元素，必须逐个计算并比较所有元素的绝对值差。
• 举个直观例子：未排序数组[7,2,9,1,5]，找最接近6的元素。不遍历所有元素的话，根本没法确定5是最接近的那个——跳过任何一个元素都可能错过真正的答案。

所以，教材里的Ω(logN)下界是有前提的（数组有序），而未排序数组的最优时间复杂度就是O(N)，必须遍历全部元素。

内容的提问来源于stack exchange，提问作者Mohi Reza