Has my code followed the appropriate logic

Question

The reason i ask this question is because i still get a null pointer exception even tho i am sure there is no issue but as usual there probably is some massive mistake i have made :D

The lecture slides said this

1) Use variables to store the start-index and length of the sequence of array elements that must contain Mike's 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 code (its the search method in the record in phonebook i am changing). Just to add, the programme loads a text file that stores names and numbers in the following formats, on seperate lines

258132 Adams, Aaron

199644 Adams, Abacuck

567480 Adams, Abraham

810323 Adams, Adam

444601 Adams, Adlard

/**
 * Write a description of class Record here.
 * 
 * @author John Bovey 
 * @version 29 September 2009
 */
public class Record
{
    private String name;
    private String number;

    public Record(String name, String number)
    {
        this.name = name;
        this.number = number;
    }

    public String getName()
    {
        return name;
    }

    public String getNumber()
    {
        return number;
    }

}

import java.io.*;
/**
 * @author John Bovey
 * @version 29 September 2009
 */
public class PhoneBook
{
    static final int MAX_RECORDS = 50000;
    private Record list[];
    private int length;

    /**
     * Constructor for objects of class PhoneBook
     */
    public PhoneBook(String file) throws FileNotFoundException
    {
        list = new Record[MAX_RECORDS];
        BufferedReader br = new BufferedReader(new FileReader(file));
        try {
            String s = br.readLine();
            length = 0;
            while (s != null) {
                String[] args = s.split(" ", 2);
                list[length] = new Record(args[1], args[0]);
                s = br.readLine();
                length++;
            }
        }
        catch (IOException e) {
        }
    }

    **/**
     * Look a name and return the number or null if there is no match
     */
       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);
               }
           }

        return list[startIndex + (length / 2)].getNumber();
    }**


    /**
     * Test the search method by looking up each name in turn
     */
     public void testSearch()
     {
         for (int i = 0; i < length; i++) {
             String name = list[i].getName();
             String num_correct = list[i].getNumber();
             String num_search = search(name);

             if (!(num_correct.equals(num_search))) {
                 System.out.printf("Failed for %s - search returned %s instead of %s\n", name, num_search, num_correct);
                 return;
            }
        }
            System.out.println("Ok.");
    }


}

Answer 1

One problem could be the length of your "list" array. You declare it of length MAX_RECORDS. Do you actually fill every element? If not, your code will look at empty elements as you search your array. Thus list[n].getName() will give a null pointer exception because list[n] is empty. This is because you're searching from list[0..MAX_RECORDS]. Further, you should only search up to (MAX_RECORDS-1).

Within your while loop in the search() method, you don't test for the case where the names match, ie. compareToIgnoreCase() returns 0. In this case you can return the match immediately.

You can combine the above with the suggestions in the other answers:

• switch to using an Array - this will give you variable array length which will make life easier
• print stack traces for your exceptions
• work on improving your search() algorithm as noted above - research binary chop
• spend some time iterating through your search algorithm on paper to be sure it does what you want
• step through using your IDE's debugger if you still can't find your problem

Hopefully all of that will get you there.

Answer 2

There could be an empty line at the end of the file that you try read. In that case args will be of size 1 and the following will throw an exception:

String[] args = s.split(" ", 2);
list[length] = new Record(args[1], args[0]);

It is good practice to first test that the line is of proper format.

Please also replace:

static final int MAX_RECORDS = 50000;
private Record list[];

with

private List<Record> list = new ArrayList<Record>();

For arrays

int length = list.length;

will return MAX_RECORDS and not the number of elements you have inserted. That is causing your exception.

Answer 3

One other thing: never swallow exceptions like this:

catch (IOException e) {
}

Whenever an IOException occurs in your code, you won't know it because you don't do anything with it. Because of that, bugs are very hard to track down because it's just like your code behaves correctly (you don't see an error after all).

At the very least print a stack trace:

catch (IOException e) {
    e.printStackTrace();
}

in which case you see some error on your console when an IOException occurs.

Answer 4

The best thing to do is fire up your IDEs debugger and step through the code and see what is happening. Learning to use your debugger will pay back huge dividends in your future projects too.

Answer 5

take a look at this line:

list[startIndex + (length / 2)].getName()

The list[startIndex + (length / 2)] might be null since you are creating the array with size MAX_RECORDS and if you are reading only 5 records on the file the rest i.e. 6th-MAX_RECORDS elements are null, so calling getName() to null should result to a NullPointerException.

If the requirement is strictly to use array, you might as well add another variable(int) ACTUAL_SIZE then increment that actual size every after valid readLine(), Lastly, your search upperbound should not be the MAX_RECORDS instead use the ACTUAL_SIZE.

Or perhaps assign this value

list[startIndex + (length / 2)]

to another variable then do a check first if the variable is not null before calling get or set.

 Object s = list[startIndex + (length / 2)];
 if(s!= null){
     //do the checking here
 }

Answer 6

While not directly related to your answer, you may want to consider using a java.util.ArrayList instead of your arrays. The ArrayList object will change its capacity to fit the amount of data you have.

This means that you won't, say, take up an entire megabyte of memory to store two phone book entries. And if you decide you want to catalogue the entire New York City phone book, you're not limited to an arbitrary maximum.