O(log n)算法用于找到具有排序i的元素与预排序列表的并集

Question

给定两个排序列表,每个包含n个实数,是否有一个O(log n)时间算法来计算两个列表的并集中排名i的元素(其中i对应于递增顺序的索引),假设元素为这两个清单是截然不同的？

编辑:@BEN:这就是我一直在做的事情,但我仍然没有得到它.

我有一个例子;

列表A:1,3,5,7列表B:2,4,6,8

找到等级(i)= 4.

第一步:i/2 = 2; 列表A现在包含的是A:1,3列表B现在包含的是B:2,4

         compare A[i] to B[i] i.e 

                 A[i] is less;

                 So the lists now become :

                   A: 3 
                   B: 2,4

第二步:i/2 = 1

         List A now contains A:3
         List B now contains B:2 

         NoW I HAVE LOST THE VALUE 4 which is actually the result ...

我知道我错过了一些东西,但即使在接近一天的思考之后,我也无法想到这一点......

Answer 1

是:

您知道该元素位于[0,i]第一个列表或[0,i]第二个列表的索引中.i/2从每个列表中取出元素并进行比较.继续进行二分法.

我没有包含任何代码,因为这个问题听起来很像家庭作业.

编辑:Bisection是二进制搜索背后的方法.它的工作原理如下:

假设i = 10; (基于零的索引,我们正在寻找整体的第11个元素).

在第一步,您知道答案是在list1(0 ... 10)或list2(0 ... 10)中.取a = list1(5)和b = list2(5).

如果a> b,则list1中有5个元素位于a之前,而list2中至少有6个元素位于a之前.所以a是结果的上限.同样,list2中有5个元素位于b之前,而list1中小于6个元素位于b之前.所以b是结果的下限.现在我们知道结果是在list1(0..5)或list2(5..10)中.如果a <b,则结果在list1(5..10)或list2(0..5)中.如果a == b我们有答案(但问题是元素是不同的,因此是!= b).

我们只需重复此过程,在每一步将搜索空间的大小减半.二分是指我们选择中间元素(平分线)超出我们知道的范围包括结果.

因此,这与二分搜索的唯一区别在于,在二进制搜索中,我们将比较我们正在寻找的值,但在这里我们将与另一个列表中的值进行比较.

注意:这实际上比O(log i)哪个更好(至少不差)O(log n).此外,对于小i(可能是i <100),实际上合并第一个i元素(线性搜索而不是二分)的操作实际上更少,因为这样更简单.当您添加缓存行为和数据位置时,线性搜索可能会快到几千.

此外,如果i> n然后依赖于结果必须朝向任一列表的末尾的事实,则每个列表中的初始候选范围来自((in).. n)