Finding an element in multiple sorted lists efficiently

Question

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) {
 tree.addAll(input);
 }
}
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));
 lists.add(list1);
 lists.add(list2);
 lists.add(list3);
 lists.add(list4);
 lists.add(list5);
 SearchItem search = new SearchItem(lists);
 System.out.println(tree);
 Integer dataOuput = search.getItem(5);
 System.out.println(dataOuput);
}

• rolfl: 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?
• david: @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 :(

Answer 1

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.

Answer 2

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