algorithm - 在有序列表中搜索

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

• 如果数组越来越大，使用binary search .这算法旨在找到一个值(或最接近的第一个值it) 在排序数组中，并在 O(logn) 中运行时间，需要遍历的元素明显少于整个列表。
  与简单的线性扫描相比，假设查询均匀分布，它将获得更好的结果(在时间性能方面)。