对已排序的多个项目进行二分搜索

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）sorted short list，结果为index

2）将短列表分为下半部分（所有小于中间元素的元素）和上半部分（所有大于中间元素的元素）。

3) 对于下半部分，我们从长列表的0to开始搜索，对于上半部分，我们从to开始搜索（n 是长列表的长度）indexindex + 1n

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