binary-search.md

Binary Searches

It seems like Binary Search is actually just a single algorithm, when that is absolutely not the case at all. There are several different variants of Binary Search all giving a different kind of target value. One that gives rightmost, another that ives leftmost, one which gives the first largest than target etc.

Smallest Element Larger than the target value

public char nextGreatestLetter(char[] letters, char target) {
    int left = 0, right = letters.length - 1, middle;
    while (left <= right) {
        middle = left + (right - left) / 2;
        if (letters[middle] <= target) left = middle + 1;
        else right = middle - 1;
    }
    return letters[left % letters.length];
}

Binary serch with left drag

Find first element equal to value or insert position. This should be used when array can have repeated values.

private static int binarySearch(int[] array, int element) {
    int left = 0, right = array.length - 1, middle;
    while (left <= right) {
        middle = left + (right - left) / 2;
        if (array[middle] == element) right = middle - 1;
        else if (array[middle] <= element) left = middle + 1;
        else right = middle - 1;
    }
    return left;
}