Performance between loop and binary search when getting data

Question

Let's say I have n number of records(key, value).

Now I want to look for x number of keys for getting their values.

Clearly seeing that if x is small, binary search is more efficient than looping through all of the records to look for the correct key. BinarySearch is a part of Arrays in Java 8. Given that my array is already sorted before performing search.

So my time complexity is O(XlogN) + O(X)
Explains:

• O(logN) is complexity of binary search
• O(X) is complexity of getting value action
• O(XlogN) dues to the number of records I want to look for

But at some point, if x becomes too big (close to value of n), it seems that just perform 1 single loop through all of my records, then comparing with all the keys I need to get values out is more efficient...

for(Record record : records){

    //Since the columns that I look for start with a specific prefix.          
    //This one is one of the factor that makes me confused 
    //when checking the performance.

    if(record.key.startWith(key-family){ 

       switch(record.key){
          case key 0:
            getvalue
            break;

          .......

          case key x:
            getvalue
            break;
       }
     }
}

For this solution, my complexity is O(N) + O(NX)
Explains:

• O(N) is complexity of the for loop
• O(NX) is complexity of switch statement and getting value out (Worst case scenario) until the looping is done.

Given that the appreance of record's key is not uniform. Some record collection will have a significant different in number of keys that start with my key-family, compares to other record collection.

My questions are:

1. How should we define when x is too big and makes binary search solution become inefficiency?

2. Is there something that I can learn from you? :)

Thank you.

Answer 1

If X is close to N binary search for X keys becomes O(N log N).

Linear search with a switch statement for X keys would seem to be N. If the switch is implemented as a pure jump table. Java uses an intelligent mix of tableswitch and tablelookup: immediate jump table and (slower) lookup in a value array. One probably must let a switch cost also O(log X), so in total also N(log N).

Now a huge switch can be done oneself by using the N values as indexes. That would be feasible if the numbers were in the range of N (or 4N); that is the array would not be too sparse.

You then could make a BitSet. Real life is seldom as nice however.

Seeing the word "record" I even would say, leave it to the database.

But there is a nice solution

If you sort the X keys, the binary search for the i^th key can start at the found/insert postion of the (i-1)^th key. Hence it is not O(N log N) but less.

ix = Arrays.binarySearch(array, ix, array.length, key);
if (ix < 0) { // Not found, insert position is -x-1 or ~x
    ix = ~ix; // Make it the insert position (x ^= -1; would do too)
}

As there is an assymetry: binary-search on an ever decreasing range, I made a symmetric recursive binary-binary-search. Not for performance, but for the algorithm.

/**
 * @param array sorted
 * @param keys sorted
 * @return found keys
 */
static Set<Integer> search(int[] array, int[] keys) {
    Set<Integer> foundKeys = new HashSet<>();
    find(foundKeys, array, 0, array.length, keys, 0, keys.length);
    return foundKeys
}

private static find(Set<Integer> foundKeys,
        int[] array, int a0, int an,
        int[] keys, int k0, int kn) {
    if (k0 < kn) {
        int k = (k0 + kn) / 2;
        int key = keys[k];
        int a = Arrays.binarySearch(array, a0, an, key);
        if (a >= 0) {
            foundKeys.add(key);
        } else {
            a = ~a;
        }
        find(foundKeys, array, a0, a, keys, k0, k);
        find(foundKeys, array, a, an, keys, k + 1, kn);
        // The overlap at a / repetition of a is due to:
        // - not found
        // - found but keys theoretically might contain doubles
    }
}

(Sorting the keys however would cost O(X log X), but the compiler did the same.)

Answer 2

1. Binary search requires input to be sorted so, this is no way an efficient solution. Assuming your input is not sorted.

2. Looping does require to go through all records.

3. Hashing of keys is something which you can look to increase performance of compare and fetch operations.

IMHO, option 3 is much better when we compare in terms of space, time complexity and the trade-offs involved. In Java you can use HashMap for most of the cases (assuming you are not dealing with issues like in big-data).