Need some help with binary chop search

Question

Hey guys,

I am trying to work ahead in my algorithms class this year :D and I am doing the class work (so its not marked or assesed as such but just for practise i suppose leading up to a piece of coursework)

Anyway - we have been given a list of names in notepad that take the following format

"surname, firsrname"

and each item is given an entry number (which at the moment is not relevant )

we are to rewrite the search method using the semi psudo code example he gave us which is where i am getting stuck. (originally the search method of the array was as follows)

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

The textual description from the lecture slides says that we can do the implementation in the following way;

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

Here is my implementation so far but i keep getting null pointer exception on

java.lang.NullPointerException at PhoneBook.search(PhoneBook.java:73) 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

Well, name could be null, or list could be null, or list[startIndex + (length / 2)] could be null, so insert checks for all of them before your line 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");
}

When you know which one is null, you can start investigating why it is null.

Btw (unrelated to your question) this code from your method contains two bugs:

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