假设我有一个长排序列表 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..
这是最有效的方法吗？有没有比这种方法收敛速度更快的方法呢？
谢谢!
最佳答案
一些建议:
1)首先，尝试找到排序后的短列表的中间元素(示例中为623)，结果为index
2) 将短列表分为下半部分(都是小于中间元素的元素)和上半部分(都是大于中间元素的元素)。
3) 对于下半部分，我们从长列表的0开始搜索到index，对于上半部分，我们从index开始搜索+ 1 到 n (n 是长列表的长度)
4) 对两半递归地执行步骤 1。
关于algorithm - 对已排序的多个项目进行二进制搜索，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30416113/