如何在创建二进制搜索算法时使用递归 [英] How to use recursion in creating a binary search algorithm

问题描述

我一直利用大学时间通过编码算法练习Java。我编码的算法之一是二进制搜索：

I have been using my time off university to practice Java through coding algorithms. One of the algorithms I coded was the binary search:

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;
            }
        }
    }
}

I我真的希望能够编写一个更清晰，更有效的二进制搜索算法，这是我编码的替代方法。我已经看到了如何使用递归的示例，例如在使用我理解的数字进行阶乘时。然而，当编写这种复杂性的东西时，我很困惑如何使用它对我有利。因此我的问题是如何在编码二进制搜索算法时应用递归。如果你有任何提示让我完善我的递归技巧，即使它必须是不考虑二元搜索的东西，那么请随时发布。

I really want to be able to write a much cleaner and efficient binary search algorithm, an alternative to what I've coded. I have seen examples of how recursion is used such as when doing factorial with numbers which I understand. However when coding something of this complexity I am confused on how to use it to my advantage. Therefore my question is how do I apply recursion when coding a binary search algorithm. And if you have any tips for me to perfect my recursion skills even if it has to be something that doesn't regard to binary search then please feel free to post.

推荐答案

如果你真的想使用递归，这应该这样做。

If you really want to use recursion, this should do it.

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);
    }
}

这篇关于如何在创建二进制搜索算法时使用递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！