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);}
Finding an element in multiple sorted lists efficiently
java;optimization;performance;algorithm;search
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 Listkeep the 'min' valuewith 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.