O (log n) to find an element having rank i in the union of pre-sorted lists

Question

For two sorted lists, each of which contains n real numbers, is there an O (log n) time algorithm for calculating the element of rank i (where I correspond to the index in ascending order) in combining the two lists, assuming the elements of the two lists are different?

EDIT: @BEN: This is what I do, but I still don't understand.

I have some examples:

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

Find rank (i) = 4.

The first step: i / 2 = 2; List A now contains A: 1, 3 List B now contains B: 2, 4

compare A[i] to B[i] ie A[i] is less; So the lists now become : A: 3 B: 2,4 

Second step: 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 ... 

I know that something is missing for me, but even after a day of close thought, I cannot simply portray it ...

Answer 1

Yes:

You know that the element is inside the index [0,i] first list or [0,i] second list. Take the i/2 element from each list and compare. Continue in half.

I do not include the code because this problem is very similar to homework.

EDIT: Bisection is a binary search method. It works as follows:

Suppose i = 10; (zero indexing, we are looking for the 11th element as a whole).

In the first step, you know that the answer is either in list1 (0 ... 10) or in list2 (0 ... 10). Take a = list1 (5) and b = list2 (5).

If a> b, then in list 1 there are 5 elements that precede a and at least 6 elements in list2 that come before a. Thus, a is the upper bound of the result. Similarly, in list2 there are 5 elements that precede b and less than 6 elements in list1 that come before b. Thus, b is the lower bound of the result. Now we know that the result will be either in list1 (0..5) or in list2 (5..10). If a <b, then the result will be either in list1 (5..10), or in list2 (0..5). And if a == b, we have our answer (but the problem says that the elements are different, so a! = B).

We simply repeat this process, reducing the size of the search space in half at each step. Bisection refers to the fact that we select the middle element (bisector) from the range, which, as we know, includes the result.

So the only difference between this and binary searches is that in binary search we compare the value we are looking for, but here we compare the value with a list of others.

NOTE: this is actually O(log i) , which is better (at least not worse) than O(log n) . In addition, for the small self (maybe I <100), there would actually be fewer operations to combine the first elements of I (linear search instead of halving), since this is much simpler. When you add cache behavior and data locality, a linear search can be faster for I to several thousand.

In addition, if i> n, then rely on the fact that the result should be at the end of one of these lists, your initial range of candidates in each list is ((in) .. n)

Answer 2

This is how you do it.

Let the first list be ListX and the second ListY . We need to find the right combination of ListX[x] and ListY[y] , where x + y = i . Since x, y, i are natural numbers, we can immediately limit our problem area to x*y . And using the equations max(x) = len(ListX) and max(y) = len(ListY) , we now have a subset of x*y elements in the form [x, y] that we need to look for.

What you will do is to arrange such elements [i - max(y), max(y)] , [i - max(y) + 1, max(y) - 1] , ..., [max(x), i - max(x)] . Then you split this list by choosing the middle combination [x, y] . Since the lists are ordered and different, you can test ListX[x] < ListY[y] . If true, then we halve the upper half of our combinations [x, y] , or if false, then we halve the lower half. You will continue to halve until you find the right combination.

There are many details that I left, but this is a common sense. This is really O (log (n))!

Edit: As Ben actually pointed out O(log(i)) . If we allow n = len(ListX) + len(ListY) , then we know that i <= n .

Answer 3

When combining two lists, you have to touch each item in both lists. If you do not touch each item, some items will be left behind. So your theoretical lower bound is O (n). Therefore, you cannot do this.

You do not have to sort, since you have two lists that are already sorted, and you can claim to be ordering as part of a merge.

Answer 4

edit: oops, I misunderstood the question. I thought this value, you want to find the rank, not vice versa. If you want to find a given rank value, then this is how to do it in O(log N) :

Yes, you can do this in O(log N) if the list allows O(1) to get random access (i.e. this is an array, not a linked list).

• Binary search on L1
• Binary search on L2
• Sum of indices

You will need to work out the math, +1, -1, what to do if the element is not found, etc., but this is an idea.