Finding an element in multiple sorted lists efficiently
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:


binary search each List
keep the 'min' value


with the code:

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