binary chop algorithm Watch

jermaindefoe
Badges: 15
Rep:
?
#1
Report Thread starter 9 years ago
#1
Hey guys, i am trying to implement a binary chop algoirthm and seem to be getting stuck and getting a null pointer but cannot see why, i am even using the lecture slides <as dictated to in the class work exercise to follow the logic>

please can someone point me in the right direction

Code:
Phonebook class
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.");
    }
    
    
}
Record class
Code:
/**
 * 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;
    }
}
the idea is that it searches the notepad file which i have attatched and return the number. we were told to follow the lecture slides and they said the following

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.

mine seems to follow this structure ?
Attached files
0
reply
markmat
Badges: 0
Rep:
?
#2
Report 9 years ago
#2
I would recommend to start with smaller list of names, some thing like 10 names. Then follow the execution in debugger: line after line to understand what it does and where it makes mistake.
0
reply
AsakuraMinamiFan
Badges: 0
Rep:
?
#3
Report 9 years ago
#3
I think you'll have to be sure it exists before comparing. For example, on the first run it should be equal to the 25000th element, but does this exist in the array list? I suspect not from looking at your text file!

Edit: to elaborate, you read the text file and add to the list by incrementing a variable. So your list indices with values looks something like this 0, 1, 2, 3, ..., 350 or how ever many there is. Any higher values (such as 25000) return null. Hence the null pointer exception when comparing!
0
reply
jermaindefoe
Badges: 15
Rep:
?
#4
Report Thread starter 9 years ago
#4
so what is the fix for this issue then as i am not quite on your wavelength
0
reply
AsakuraMinamiFan
Badges: 0
Rep:
?
#5
Report 9 years ago
#5
Set the length of the array to the number of lines in the text file. (Assuming you can do this with static arrays in Java, I'm not sure...)

Edit: for example, in search() you could set the length to 346 (number of lines in the text file) and then reverse the > 0 to a < 0. Then it works okay.

Of course, this is no good if you change the number of lines in a text file, so it's up to you to figure out how to either: make the array list[] to the same number of elements in the text file; or alternatively, use a data structure which expands as you add to it.

Edit 2: or just change length = list.length to length = this.length since you've already counted it.
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

The new Gillette ad. Is it:

Man-hating bullsh*t (1)
20%
Pro-humanity (4)
80%

Watched Threads

View All
Latest
My Feed

Oops, nobody has posted
in the last few hours.

Why not re-start the conversation?

Start new discussion

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise