将二进制搜索转换为使用递归

Question

我正在我的程序中实现这个二进制搜索算法，它实现了 Comparator 接口。本质上，我想让这个方法递归，但我一直没有这样做。我想知道这样做是否合适。

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[].
}

Answer 1

您将 high 和 low 传递给该方法。创建采用这些附加参数的方法的另一个版本，使其成为 private 并使用 0 和 a.length - 1 调用它以获得新参数。喜欢，

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

然后简单地用递归调用替换循环。喜欢，

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[].
}

将二进制搜索转换为使用递归

Convert binary search to use recursion

java

arrays

binary-search