Besoin d'aide avec la recherche de hachage binaire

Question

J'essaie de travailler dans mon cours d'algorithmes cette année: D et moi faisons le travail de classe (donc ce n'est pas marqué ou évalué en tant que tel mais juste pour la pratique je suppose conduisant à un morceau de cours)

Quoi qu'il en soit - nous avons donné une liste de noms comme un fichier texte qui prennent le format suivant

"surname, first name" 

et chaque élément est donné un numéro d'entrée (qui, au moment n'est pas pertinent)

nous devons réécrire la méthode de recherche en utilisant le semi-p exemple de code sudo il nous a donné qui est où je suis coincé. (À l'origine de la méthode de recherche du tableau se présente comme suit)

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

La description textuelle de la glisse conférence dit que nous pouvons faire la mise en œuvre de la manière suivante;

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 

Voici ma mise en œuvre à ce jour, mais je continue à obtenir NullPointerException sur

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

Eh bien, name pourrait être nulle, ou list pourrait être nulle, ou list[startIndex + (length/2)] pourrait être nul, donc insérer des contrôles pour chacun d'eux avant la ligne 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"); 
} 

Quand vous savez que l'on est nul, vous pouvez commencer à enquêter sur la raison pour laquelle il est nul.

BTW (sans rapport avec votre question) ce code de votre méthode contient deux bugs:

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

Answer 2

Si l'on suppose que le code est aussi donné et le NPE est jeté dans search, le ne peut-être l'explication est que l'une des entrées à la méthode search est invalide:

• name est null,
• list est null, ou
• l'un des éléments de list est null.

Vous avez donc besoin de regarder le code qui appelle search pour la cause principale.

(Cela ne veut pas dire que search est nécessairement exacte. Mais vous devez résoudre le problème ci-dessus en premier.)