# Efficiently find an element in multiple sorted lists

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. I came up with below code..

Can we do it much better? So that is the reason I am opting for code review..

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
You have changed your question substantially. The code does a completely different thing now. In order to prevent invalidating existing answers, it is customary on CodeReview to either update your answer and append your revised code, or, if you want different code reviewed, you should ask a new question. –  rolfl Feb 28 at 3:20
Sure.. How do I revert my changes to old changes..? And then let me ask new question.. –  user2809564 Feb 28 at 3:22
Thanks.. You reverted to my old change.. Let me ask a new question then.. I have created a new question here. –  user2809564 Feb 28 at 3:24

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 (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);
}
`
-