java - 在二进制印章搜索方面需要一些帮助

我正在尝试今年的算法课：D，并且正在做这堂课的工作（因此，它没有被标记或评估，只是为了练习，我认为这是一部分课程）

无论如何-我们已经获得了名称列表作为文本文件，格式如下

"surname, first name"

并且每个项目都有一个条目号（目前不相关）

我们将使用他给我们的半伪代码示例重写搜索方法，这就是我遇到的问题。 （最初，数组的搜索方法如下）

/**
 * Look a name and return the number or null if there is no match
 */
public String search(String name)
{
    for (int i = 0; i < length; i++) {
        if (name.equals(list[i].getName())) {
            return list[i].getNumber();
        }
    }
    return null;
}

讲座幻灯片中的文字说明说，我们可以通过以下方式进行实现：

1) Use variables to store the start-index and length of the sequence of array elements that must contain this entry if there is one.
2) Set start-index to 0 and length to the array length.
3) while length is greater than 1
a) Compare Mike with the name in the middle element (at start_index + length/2)
b) If it is earlier then set length to length/2 and leave start-index as it is.
c) If it is later or equal then add length/2 to start-index and subtract length/2 from length
4) length is now 1 so it must be Mike's entry if he has one

到目前为止，这是我的实现，但是我不断收到null指针异常

java.lang.NullPointerException
    at PhoneBook.search(PhoneBook.java:73) (if(name.comeToIgnoreCase... )
    at PhoneBook.testSearch(PhoneBook.java:57)

public String search (String name)
    {
        int startIndex = 0;
        int length = list.length;

        while(length > 1){
            if(name.compareToIgnoreCase(list[startIndex + (length / 2)].getName()) > 0) {
                length = length / 2;
            }
            else {
                startIndex = startIndex + (length / 2);
                length = length - (length / 2);
            }
            if (length == 1){
                return list[length].getName();
            }
        }

        return null;
    }

最佳答案

好吧，name可以为空，或者list可以为空，或者list[startIndex + (length / 2)]可以为空，因此在第57行之前插入对所有这些的检查：

if (null == name)  throw new NullPointerException ("name is null");
if (null == list)  throw new NullPointerException ("list is null");
if (null == list[startIndex + (length / 2)]) {
    throw new NullPointerException ("list[" + (startIndex + (length / 2)) + "] is null");
}

当您知道哪个为空时，就可以开始调查为什么它为空。

顺便说一句（与您的问题无关）方法中的此代码包含两个错误：

if (length == 1){
    return list[length].getName();
}

关于java - 在二进制印章搜索方面需要一些帮助，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1526043/