java - BinarySearch 实现在某些情况下不起作用

Question

我是一名 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("");
    }

我试图从这个链接复制它http://en.wikipedia.org/wiki/Binary_search_algorithm并尝试让它适用于列表。

输入列表是[1, 2, 3, 4, 5, 7, 9]

如果我搜索键 2 输出是 1 这很好，但是如果我尝试例如 1 则会触发 SearchException .

我无法解释为什么。我尝试通过在纸上重现代码来调试代码，但它在纸上有效。

谢谢!

Answer 1

您目前对 max 是否为包含下限存在不一致，如此处所建议:

int max = list.size()-1;
...
max = mid - 1;

或唯一下限，如此处所建议:

while (max > min)

只要您始终如一，您就可以使它以任何一种方式发挥作用。我个人建议使用独占上限，因为这与 list.size() 和一般的计算机科学一致。所以如果mid太大，需要将max改为equalmid。您的代码将如下所示:

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。看看您是否喜欢它。)