Convert binary search to use recursion-CodePudding

I'm implementing this Binary Search algorithm in my program, which implements the Comparator interface. Essentially, I want to make this method recursive, but I've been failing at doing so. I wonder if it's appropriate to even do that.

public static <Key> int firstIndexOf(Key[] a, Key key, Comparator<Key> comparator) {
    if (a == null || key == null || comparator == null) {
        throw new NullPointerException("Arguments cannot be null.");
    }
    int low = 0,
        high = a.length - 1;
    if (comparator.compare(a[0], key) == 0) {
        return 0;   // Non-recursive base case.
    }
    while (low <= high) {
        int mid = low   (high - low) / 2;
        // For key, we are searching for the first occurrence.
        // Comparator: compare the key is being sorted with.
        if (comparator.compare(key, a[mid]) < 0) high = mid - 1;
        else if (comparator.compare(key, a[mid]) > 0) low = mid   1;
        else if (comparator.compare(a[mid - 1], a[mid]) == 0) high = mid - 1;
        
        else return mid;
    }
    return -1;      // Index of the first occurrence of an element matching key in a[].
}

CodePudding user response：

You pass high and low to the method. Create another version of the method that takes those additional arguments, make it private and invoke it with 0 and a.length - 1 for the new arguments. Like,

public static <Key> int firstIndexOf(Key[] a, Key key, Comparator<Key> comparator) {
    return firstIndexOf(a, key, comparator, 0, a.length - 1);
}

Then simply replace the loop with recursive calls. Like,

private static <Key> int firstIndexOf(Key[] a, Key key, Comparator<Key> comparator, int low, int high) {
    if (a == null || key == null || comparator == null) {
        throw new NullPointerException("Arguments cannot be null.");
    }
    if (comparator.compare(a[0], key) == 0) {
        return 0; // Non-recursive base case.
    }
    if (low <= high) {
        int mid = low   (high - low) / 2;
        // For key, we are searching for the first occurrence.
        // Comparator: compare the key is being sorted with.
        if (comparator.compare(key, a[mid]) < 0)
            return firstIndexOf(a, key, comparator, low, mid - 1);
        else if (comparator.compare(key, a[mid]) > 0)
            return firstIndexOf(a, key, comparator, mid 1, high);
        else if (comparator.compare(a[mid - 1], a[mid]) == 0)
            return firstIndexOf(a, key, comparator, low, mid - 1);
        else
            return mid;
    }
    return -1; // Index of the first occurrence of an element matching key in a[].
}