在有序列表中搜索

Question

假设我们有一个按升序排序的列表0,10,30,45,60,70.给定一个数字X如何在下面的列表中找到它的数字呢？

我正在寻找最有效(更快)的算法来做到这一点,当然不必迭代整个列表.

Ex: [0, 10, 30, 45, 60, 70]

Given the number 34, I want to return 30.
Given the number 30, I want to return 30.
Given the number 29, I want to return 10.

等等.

Answer 1

• 如果你的列表确实那么小,最有效的方法是创建一个大小为71的数组,用它初始化一次arr[i] = answer,并在不断的查询时间内 - 得到答案.这个想法是因为您可能的查询集非常有限,没有理由不预先计算它并从预先计算的数据中获得结果.

• 如果你不能进行预处理,并且阵列很小 - 线性扫描对于如此小的阵列将是最有效的,那么使用复杂算法的开销对于这样的小阵列来说是不值得的.对于小型数组,每次迭代添加大量指令的更复杂算法(如二进制搜索)的任何开销都是无效的.请注意log_2(6) < 3,这也是在线性搜索中获得结果的预期时间(假设均匀分布),但线性搜索要简单得多,每次迭代都比二进制搜索快得多.

伪代码:

prev = -infinity
for (x in arr):
   if x>arr: 
       return prev
   prev = x

• 如果数组变大,请使用二进制搜索.此算法旨在查找已排序数组中的值(或最接近它的第一个值),并在O(logn)时间上运行,需要遍历的元素明显少于整个列表.
  假设查询的分布均匀,与初始线性扫描相比,它将获得更好的结果(在时间性能方面).