java需要一些关于二进制切块搜索的帮助

Question

今年我试图在我的算法课上取得领先：D，我正在做课堂作业（因此，它没有被标记或评估为这样，只是为了练习，我想是为了准备一个课程作业）

无论如何-我们已经收到了一个名称列表作为文本文件，采用以下格式

"surname, first name"

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

我们将使用他给我们的半psudo代码示例重写搜索方法，这正是我陷入困境的地方。（原来数组的搜索方法如下）

/**
 * 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

这是到目前为止我的实现，但我一直在上得到空指针异常

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;
    }

Answer 1

假设代码是给定的，NPE被抛出search，唯一的解释可能是search方法的一个输入无效：

• name是null
• list是null，或
• list的元素之一是null

因此，您需要查看调用search以查找根本原因的代码

（这并不是说search一定是正确的。但是你需要先解决上面的问题。）

Answer 2

嗯，name可以为null，或者list可以为null，或者list[startIndex + (length / 2)]可以为null，所以在第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");
}

当你知道哪一个是空的，你可以开始调查为什么它是空的

顺便说一句（与你的问题无关）你方法中的这段代码包含两个bug：

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