一尘不染

如何在创建二进制搜索算法中使用递归

algorithm

我上大学期间一直在通过编码算法来练习Java。我编码的算法之一是二进制搜索:

public class BinarySearch {

    private static int list[] = {3, 6, 7, 8, 9, 10};

    public static void main(String[] args) {
        BinarySearch b = new BinarySearch();
        b.binarySearch(list);

    }

    public void binarySearch(int[] args) {
        System.out.println("Binary search.");

        int upperBound = args.length;
        int lowerBound = 1;
        int midpoint = (upperBound + lowerBound) / 2;
        int difference = upperBound - lowerBound;

        int search = 7;

        for (int i = 0; i < args.length; i++) {
            if (search < args[midpoint - 1] && difference != 1) {
                upperBound = midpoint - 1;
                midpoint = upperBound / 2;
            } else if (search > args[midpoint - 1] && difference != 1) {
                lowerBound = midpoint + 1;
                midpoint = (lowerBound + upperBound) / 2;

            } else if (search == args[midpoint - 1]) {
                midpoint = midpoint - 1;

                System.out.println("We found " + search + " at position " + midpoint + " in the list.");
                i = args.length;
            } else {
                System.out.println("We couldn't find " + search + " in the list.");
                i = args.length;
            }
        }
    }
}

我真的希望能够编写一种更简洁,有效的二进制搜索算法,以替代我编写的代码。我已经看到了如何使用递归的示例,例如使用我理解的数字进行阶乘时。但是,当编写这种复杂的代码时,我对如何利用它感到困惑。因此,我的问题是编码二进制搜索算法时如何应用递归。如果您有什么技巧可以完善我的递归技能,即使它不必与二进制搜索无关,也请随时发表。


阅读 210

收藏
2020-07-28

共1个答案

一尘不染

如果您确实要使用递归,则应该这样做。

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

public static int binarySearch(int[] a, int start, int end, int target) {
    int middle = (start + end) / 2;
    if(end < start) {
        return -1;
    }

    if(target==a[middle]) {
        return middle;
    } else if(target<a[middle]) {
        return binarySearch(a, start, middle - 1, target);
    } else {
        return binarySearch(a, middle + 1, end, target);
    }
}
2020-07-28