BinarySearch 实现在某些情况下不起作用
BinarySearch Implementation does not work in certain cases
我是 java 初学者,我正在尝试编写二进制搜索算法的实现代码。
这是我的代码:
protected int doSearch(List<Integer> list, int key) throws SearchException{
int min = 0;
int max = list.size()-1;
while(max > min){
int mid = min + ((max-min)/2);
if(list.get(mid)==key){
return mid;
}
else if(list.get(mid) < key){
min = mid +1 ;
}
else{
max = mid - 1;
}
}
throw new SearchException("");
}
我试图从这个 link http://en.wikipedia.org/wiki/Binary_search_algorithm 复制它并试图让它适用于列表。
输入列表为[1, 2, 3, 4, 5, 7, 9]
如果我搜索键 2
,输出是 1
,这很好,但是如果我尝试 1
,则会触发 SearchException。
我无法解释为什么。我试图通过在纸上重现来调试代码,但它在纸上起作用了。
谢谢!
您目前对 max
是否为 包含 下限存在不一致,如此处所建议:
int max = list.size()-1;
...
max = mid - 1;
或 独占 下限,如此处所建议:
while (max > min)
只要您始终如一,您就可以使它以任何一种方式发挥作用。就我个人而言,我建议使用独占上限,因为这与 list.size()
和一般的计算机科学是一致的。所以如果mid
太大,需要把max
改成等于mid
。您的代码将如下所示:
int max = list.size(); // Note change here
while(max > min) {
int mid = min + ((max - min) / 2);
if (list.get(mid) == key) {
return mid;
} else if (list.get(mid) < key) {
min = mid +1 ;
} else {
max = mid; // Note change here
}
}
(我修改了格式,以使其也更易于阅读 IMO。看看您是否喜欢。)
最简单的解决方法是更改:
while (max > min) {
至:
while (max >= min) {
你在上面抛出异常是因为你没有处理那个情况。
我是 java 初学者,我正在尝试编写二进制搜索算法的实现代码。
这是我的代码:
protected int doSearch(List<Integer> list, int key) throws SearchException{
int min = 0;
int max = list.size()-1;
while(max > min){
int mid = min + ((max-min)/2);
if(list.get(mid)==key){
return mid;
}
else if(list.get(mid) < key){
min = mid +1 ;
}
else{
max = mid - 1;
}
}
throw new SearchException("");
}
我试图从这个 link http://en.wikipedia.org/wiki/Binary_search_algorithm 复制它并试图让它适用于列表。
输入列表为[1, 2, 3, 4, 5, 7, 9]
如果我搜索键 2
,输出是 1
,这很好,但是如果我尝试 1
,则会触发 SearchException。
我无法解释为什么。我试图通过在纸上重现来调试代码,但它在纸上起作用了。
谢谢!
您目前对 max
是否为 包含 下限存在不一致,如此处所建议:
int max = list.size()-1;
...
max = mid - 1;
或 独占 下限,如此处所建议:
while (max > min)
只要您始终如一,您就可以使它以任何一种方式发挥作用。就我个人而言,我建议使用独占上限,因为这与 list.size()
和一般的计算机科学是一致的。所以如果mid
太大,需要把max
改成等于mid
。您的代码将如下所示:
int max = list.size(); // Note change here
while(max > min) {
int mid = min + ((max - min) / 2);
if (list.get(mid) == key) {
return mid;
} else if (list.get(mid) < key) {
min = mid +1 ;
} else {
max = mid; // Note change here
}
}
(我修改了格式,以使其也更易于阅读 IMO。看看您是否喜欢。)
最简单的解决方法是更改:
while (max > min) {
至:
while (max >= min) {
你在上面抛出异常是因为你没有处理那个情况。