# Finding an element in multiple sorted lists efficiently

I have $k$ sorted Lists, each of size $n$. Currently I have hard-coded 5 sorted Lists each of size 3, but in general that is configurable.

I would like to search for single element in each of the $k$ Lists (or its predecessor, if it doesn't exist).

Obviously I can binary search each List individually, resulting in a $O(k*log(n))$ runtime. But I think we can do better than that: after all, we're doing the same search $k$ times.

Could this be improved?

private static TreeSet<Integer> tree = new TreeSet<Integer>();

public SearchItem(final List<List<Integer>> inputs) {
tree = new TreeSet<Integer>();
for (List<Integer> input : inputs) {
}
}

public Integer getItem(final Integer x) {
if(tree.contains(x)) {
return x;
} else {
return tree.higher(x);
}
}

public static void main(String[] args) {
List<List<Integer>> lists = new ArrayList<List<Integer>>();

List<Integer> list1 = new ArrayList<Integer>(Arrays.asList(3, 4, 6));
List<Integer> list2 = new ArrayList<Integer>(Arrays.asList(1, 2, 3));
List<Integer> list3 = new ArrayList<Integer>(Arrays.asList(2, 3, 6));
List<Integer> list4 = new ArrayList<Integer>(Arrays.asList(1, 2, 3));
List<Integer> list5 = new ArrayList<Integer>(Arrays.asList(4, 8, 13));

SearchItem search = new SearchItem(lists);
System.out.println(tree);

Integer dataOuput = search.getItem(5);

System.out.println(dataOuput);
}

-
Question: In your text you say: I would like to search for single element in each of the k Lists (or its predecessor, if it doesn't exist). but in your code you get the *successor* not the predecessor. Which one is right? –  rolfl Feb 28 at 2:00
@rolfl: I just updated the question.. I miss couple of important points.. I have rewrote most of the things.. Now take a look.. It will make sense now.. I guess now you will be angry as in the question lot of things might have change as corresponding to what you have suggested :( –  user2809564 Feb 28 at 3:05

I think you have some misguided assumptions here.

For a start, what you have now is not $O(k \log(n))$, it first scans and sorts all the data in to the tree, which is a $O(N \log(N))$ operation, where $N$ is the cumulative data size (sum of input-array sizes). Then, the check on it, is a $O(\log(N))$ check, so, your algorithm is in the order of $O(N\log(N))$.

The complexity you are worried about $O(k\log(n))$ is really quite trivial. $k$ is a small number (5), and log(n) is always small... in many ways, after n = 128 it is effectively a constant....

So, I would do the following:

1. binary search each List
2. keep the 'min' value

with the code:

Integer result = null;
for (List<Integer> data : lists) {
int pos = Collections.binarySearch(data, input);
if (pos >= 0) {
//exact match, return
return data.get(pos);
}
pos = -pos - 1;
if (pos < data.size()) {
Integer found = data.get(pos);
if (result == null || result.compareTo(found) > 0) {
result = found;
}
}
}
return result;


Now, if you wanted to be fancy, and you wanted the fastest response times, you could put each binary search in to a Callable<Integer>, and run them in parallel....

Then rank the results, and teturn it all in time complexity $O(\log(n))$ assuming $k$ is less than your hardware CPU count.

-

Two quick notes about the code in the question:

1. A bug: a client could create more than one instance of the class but all of them will use the same TreeSet instance since it's static.

2. public Integer getItem(final Integer x) {
if(tree.contains(x)) {
return x;
} else {
return tree.higher(x);
}
}


The following is the same:

public Integer getItem(final Integer x) {
return tree.ceiling(x);
}
`
-