在这种情况下,值匹配并且boolean的值设置为true,但是返回被调用两次并且将值更新为false。任何人都可以建议我在这里缺少什么?
public class BinSearch {
public static void main(String[] args) {
BinSearch bin=new BinSearch();
int arr[]= {2,4,6,8,10,12,14,16};
boolean b=bin.binSearch(arr,0,arr.length-1,12);
System.out.println("Number found "+b);
}
public boolean binSearch(int arr[],int low,int high,int val)
{
int mid=(low+high)/2;
if(arr[mid]==val)
{
return true;
}
else if(arr[mid]>val)
{
binSearch(arr,mid+1,high,val);
}
else
{
binSearch(arr,low+1,mid,val);
}
return false;
}
}
调用递归时,您丢失了两个返回值:
return binSearch(...);
如果你不写它们,该方法将忽略递归的结果,并在最后返回false
。在这之后,最后的return
将是不必要的,应该被删除。最后,你需要检查low > high
时的情况,这意味着找不到该元素。
因为你的return false;
会覆盖除第一次运行时找到值的情况以外的所有内容,并且不会调用任何递归调用。请返回每个递归电话。此外,您必须检查您的低边界是否小于或等于高边界。所以,你的代码可能如下:
public boolean binSearch(int arr[],int low,int high,int val)
{
if (low <= high) {
int mid=(low+high)/2;
if(arr[mid]==val) {
return true;
} else if(arr[mid]>val) {
return binSearch(arr,mid+1,high,val);
} else {
return binSearch(arr,low+1,mid,val);
}
}
return false;
}
您还可以在binSearch
函数中尝试以下代码。唯一的变化是有一个布尔类型变量捕获递归调用中返回的值,最后返回此变量。
public boolean binSearch(int arr[],int low,int high,int val) {
int mid=(low+high)/2;
boolean returnValue = false;
if(arr[mid]==val) {
return true;
} else if(arr[mid]>val) {
returnValue = binSearch(arr,mid+1,high,val);
} else {
returnValue = binSearch(arr,low+1,mid,val);
}
return returnValue;
}
public class BinSearch {
public static void main(String[] args) {
BinSearch bin=new BinSearch();
int arr[]= {2,4,6,8,10,12,14,16};
boolean b=bin.binSearch(arr,0,arr.length-1,16);
System.out.println("Number found "+b);
}
public boolean binSearch(int arr[],int low,int high,int val)
{
int mid=(low+high)/2;
//boolean b = false;
while(low<=high)
{
if(arr[mid]==val)
{
return true;
}
else if(val>arr[mid])
{
return binSearch(arr,mid+1,high,val);
}
else
{
return binSearch(arr,low+1,mid,val);
}
}
return false;
}
}