java - Last index of multiple keys using binary-search?

Question

i have multiple occurrences of a key in a sorted array, and i want to perform binary search on them, a normal binary search returns some random index for the key having multiple occurrences, where as i want the index of the last occurrence of that key.

int data[] = [1,2,3,4,4,4,4,5,5,6,6];
int key = 4;
int index = upperBoundBinarySearch(data, 0, data.length-1, key);

Index Returned = 6

Answer 1

The Java implementation in this answer finds the first occurrence of a key. There's a comment about how this could be changed to find the last occurrence, but the suggestion results in an infinite loop. The idea seems sound, though.

EDIT: After some research, I found a neat solution on The Algo Blog. Since the first found match is not necessarily the needed one, you need to keep track of the "best" match so far. When you do get a match, you store it and continue with the binary search on the right of that match (low = mid + 1).

public static int binarySearch(int[] a, int key) {
    return binarySearch(a, 0, a.length, key);
}

private static int binarySearch(int[] a, int fromIndex, int toIndex,
        int key) {
    int low = fromIndex;
    int high = toIndex - 1;
    int found = -1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];

        if (midVal < key) {
            low = mid + 1;
        } else if (midVal > key) {
            high = mid - 1;
        } else {
            found = mid;
            // For last occurrence:
            low = mid + 1;
            // For first occurrence:
            // high = mid - 1;
        }
    }
    return found;
}

This change keeps the O(log n) complexity. Still, the actual performance depends on the application. When the length of the array is much larger than the amount of duplications of the sought key, a linear search for the last occurrence may be faster. When there are a lot of duplications though, this modified binary search is probably preferable.