binaire Rechercher compareTo objets String

Question

class ObjectBinarySearcher{ 

    public static int search(String[] array, String value){ 

     int first = 0, last = array.length-1, position = -1; 
     boolean found = false; 

     while(!found && first < last){ 
      int mid = (first+last)/2; 
      int midValue = array[mid].compareTo(value); 

      if(midValue==0){ 
       position = mid; 
       found = true; 
      } 
      else if(midValue<0) 
       last = mid-1; 
      else 
       first = mid+1; 
     } 

     return position; 
    } 
} 

J'envoie un tableau contenant { « amour », « haine », « heureux », « triste », « neutre »}, et chaque fois que je tente d'utiliser ma recherche binaire méthode pour rechercher "neutre", Il me dit qu'il n'est pas trouvé. Qu'est-ce qui cause cela?

Answer 1

Changer le while loop à while(!found && first <= last)

Answer 2

1. Votre tableau d'entrée doivent être triés afin d'utiliser la recherche binaire. Comme @Libby l'a fait remarquer, votre boucle while doit être modifiée pour permettre que la première soit inférieure ou égale à la dernière.

2. Vous devez être en mesure de quitter la boucle s'il n'y a aucune correspondance trouvée lorsque first == last.

3. Si midValue < 0, vous devez déplacer la borne inférieure, et non la borne supérieure (et vice versa).

Nouveau code:

while (!found && first <= last) { // allow first to be lower or equal to last 
    int mid = (first + last)/2; 
    int midValue = array[mid].compareTo(value); 

    if (midValue == 0) { // matched! 

     position = mid; 
     found = true; 

    } else if (first == last) { // didn't match and there was only one left to check 

     break; // so break out of the loop 

    } else if (midValue < 0) { // current pos is too low 

     first = mid + 1; // so adjust the lower bound 

    } else { // current pos is too high 

     last = mid - 1; // so adjust the upper bound 

    } 
}