二进制搜索：程序不会终止

Question

我一直在尝试学习算法，作为其中的一部分，我一直在尝试编写二进制搜索代码，逻辑似乎很好。代码不会终止并且 IDE 永远保持空闲状态。我不明白我做错了什么。任何帮助表示赞赏。提前致谢！

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int no = 5;
        System.out.print(binSearch(arr, no, 0, arr.length - 1));


    }

    private static boolean binSearch(int[] arr, int no, int start, int end) {
        while(start <= end) {
            int mid = (start + end) / 2;
            if (arr[mid] == no) {
                return true;
            } else if (no > arr[mid]) {
                binSearch(arr, no, mid + 1, end);
            } else if(no < arr[mid]) {
                binSearch(arr, no, start, mid - 1);
            }
        }
        return false;
    }
}

Answer 1

您在两个递归调用中缺少 return：

private static bool binSearch(int[] arr, int no, int start, int end) {
    
    while(start <= end) {
        int mid = (start + end) / 2;
        if (arr[mid] == no) {
            return true;
        } else if (no > arr[mid]) {
            return binSearch(arr, no, mid + 1, end);
        } else if(no < arr[mid]) {
            return binSearch(arr, no, start, mid - 1);
        }
    }
    return false;
}

你也可以考虑写成非递归循环。

Answer 2

好的，我想我们回顾一下递归

binSearch(arr, num, start, end){

    while (start<=end){
        int mid = (start+end)/2;
        if (arr[mid] == no) {
           return true              #when it finally matches return true 
        }


        else if (arr[mid] > no) {
            binSearch(arr, no, start, mid-1)  #call binSearch for new value

        }
    }
}

只是为了说明递归，假设我们需要一些值 B 作为输入 A。现在想象一个节点或某个点作为代表我们输入 A 的原点。 A 之后的每个点或节点都是我们为找到值 B.

而采取的一些步骤

一旦我们找到了我们想要的值，我们的方法的结构就可以用一个单一方向的图来说明。 A --> C --> --> D --> B

递归本质上就是这样工作的。现在首先，让我们看一下您的 else if 语句。当您的参数满足 else if 条件之一时，您将调用 binSearch 方法。

这样做基本上是创建一个新的原点，而不是处理最初的原点。所以假设在第 3 次迭代中你终于满足了你的布尔条件并且它 returns true。但是 return 哪里是真的？

仅对 binSearch 进行的最后一次调用或最近一次调用。让我们称之为迭代 2。

现在，一旦设置了 return 值，它就会简单地移动到下一个代码块，这将我们带到您的 while 循环。您的代码可以移动到下一个代码块（returning 假值）的唯一方法是跳出 while 循环，即。让您的起始值大于最终值。

但请记住，我们正在进行第 2 次迭代。第 2 次迭代被赋予了满足 while 循环的开始和结束值，因此它再次循环，并且在最终迭代之前第 2 次迭代到达的其他任何 else-if 语句return是的，它将无限期地重复。

上面提到的显而易见的解决方案是在调用之前放置 'return'，因为这将 return 一直回到对 binSearch 的原始调用。

此外，while 循环不是必需的，除非您不使用递归。

二进制搜索：程序不会终止

Binary Search: Program doesn't terminate

algorithm

binary-search