二叉搜索：程序不会终止

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

为了说明递归，假设我们想要输入A的某个值B。现在想象一个节点或某个点作为原点，表示我们的输入a。对于A之后的每一个点或节点，我们朝着找到值B迈出了一步。

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

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

这基本上是创建一个新的原点，而不是处理最初的原点。假设在第3次迭代中，您终于满足了布尔条件，它返回true。但它又回到了哪里呢？

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

现在，一旦返回值被生成，它就简单地移动到下一个代码块，这将使我们进入while循环。你的代码可以转移到下一个代码块(返回错误值(的唯一方法是打破while循环，即让你的起始值大于结束值。

但请记住，我们正在进行迭代2。迭代2被赋予了满足while循环的开始和结束值，因此它再次循环，如果语句迭代2在返回true的最后一次迭代之前到达，它将无限期地重复。

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

此外，while循环是不必要的，除非您在没有递归的情况下执行它。