我已经写了这个基于递归的二进制搜索算法,但是我不能理解错误的原因。
// Only a sorted array must be entered for binary search to work
public int binarySearch(int searchFor, int[] inArray, int from, int to){
if (to >= from){
int mid = (to-from)/2 + from;
if (inArray[mid] == searchFor){
return inArray[mid];
} else if (inArray[mid] < searchFor){
binarySearch(searchFor, inArray, ++mid, to);
} else if (inArray[mid] > searchFor){
binarySearch(searchFor, inArray, from, ++mid);
}
}
return -1;
}
线程“main”java.lang.StackOverflowerr中出现异常
at search.binarySearch(search.java:24)
at search.binarySearch(search.java:24)
at search.binarySearch(search.java:24)
at search.binarySearch(search.java:24)
2条答案
按热度按时间fslejnso1#
一些问题和评论:
在最后一种情况下,值
++mid
是错误的binarySearch
. 该值应小于1mid
那样的话。我也会投票反对使用
++mid
或者--mid
这表明mid
更改不需要的值。你应该过去mid+1
在第一种情况下mid-1
在第二个。binarySearch
返回一个int
,但是当您的代码递归调用它时,它不会对该返回值执行任何操作。您应该返回该值。所以:
表达式
(to-from)/2 + from
是一种冗长的做法(from+to)/2
...xam8gpfp2#
除了添加
return
到的递归调用binarySearch
,逻辑上有几个缺陷:mid
应递减以捕捉左侧部分中的值:应该有一张有效的支票
mid
,from
,to
输入数组中的值因此,该方法应如下所示:
测验:
输出: