algorithm - 对已排序的多个项目进行二进制搜索

Question

假设我有一个长排序列表 L={1, 2,.., 999, 1000} 和一个短排序列表 S={22, 255, 623, 732, 876}。

在 L 中，我想搜索 S 的每个元素。最有效的方法是什么？

目前我想到的方法是:

1. Binary search for 22. Record the lower bound=23
2. Binary search for 876. Record the upper bound=875
3. Binary search for 255 in the range [lower bound=23, upper bound=875].
4. Set lower bound=256, and go on..

这是最有效的方法吗？有没有比这种方法收敛速度更快的方法呢？

谢谢!

Answer 1

一些建议:

1)首先，尝试找到排序后的短列表的中间元素(示例中为623)，结果为index

2) 将短列表分为下半部分(都是小于中间元素的元素)和上半部分(都是大于中间元素的元素)。

3) 对于下半部分，我们从长列表的0开始搜索到index，对于上半部分，我们从index开始搜索+ 1 到 n (n 是长列表的长度)

4) 对两半递归地执行步骤 1。