La recherche binaire générique échoue à l'aide d'une clé de caractères consécutifs

Question

J'ai une recherche binaire générique qui semble fonctionner correctement avec Integer s. Toutefois, lorsque j'essaie de l'utiliser avec String s il se bloque parfois, présentant un ArrayIndexOutOfBoundsException à différentes lignes; surtout je spécifie la clé avec un mot en utilisant la même lettre plus d'une fois. Par exemple String key = "peach"; renvoie l'index correct, String key = "blueberry"; est introuvable et String key = "scoop"; provoque une défaillance. Il semble avoir à faire avec (key.equals(list[mid])) en T, mais je ne peux pas donner de sens. Merci de votre aide.

public class BinarySearch { 

private BinarySearch() { } 

private static <T extends Comparable<? super T>> int search(T[] list, int first, int last, T key){ 
    int foundPosition; 
    int mid = first + (last - first)/2; 
    if (first > last) 
     foundPosition = -1; 
    else if (key.equals(list[mid])) 
     foundPosition = mid; 
    else if (key.compareTo(list[mid]) < 0) 
     foundPosition = search(list, first, mid - 1, key); 
    else 
     foundPosition = search(list, mid + 1, last, key); 

    return foundPosition; 
} 

public static void main(String args[]) { 

Integer [] a = {0,2,4,6,8,10,12,14,16}; 
int finalIndex = 9; 
System.out.println("Integer test array contains..."); 
    for (Integer a1 : a) { 
     System.out.print(a1 + " "); 
    } 
int result; 
for (int key = -4; key < 11; key++) { 
    result = BinarySearch.search(a, 0, finalIndex, key); 
    if (result < 0) 
     System.out.println("\n" + key + " is not in the array."); 
    else 
     System.out.println("\n" + key + " is at index " + result + "."); 
} 

String[] searchFruits = {"lemon", "apple", "banana", "peach", "pineapple", "grapes", "blueberry", "papaya"}; 
System.out.println("\nChecking fruits..."); 
System.out.println("String test array contains..."); 
for (String a1 : searchFruits) { 
     System.out.print(a1 + " "); 
    } 
int fruit = 8; 
int fresult; 
String key = "blueberry"; 
    fresult = BinarySearch.search(searchFruits, 0, fruit, key); 
    if (fresult < 0) 
     System.out.println("\n" + key + " is not in the array."); 
    else 
     System.out.println("\n" + key + " is at index " + fresult + "."); 
} 

}

Answer 1

Le problème est que vous utilisez la taille du tableau en tant que votre index, conduisant à l'indice de tableau hors question des limites.

Plus précisément

int finalIndex = 9; 

et

int fruit = 8; 

Maintenant, la raison pour laquelle vous ne voyez que l'exception des moments dépend de quelle manière la recherche binaire va. Si la valeur que vous recherchez est < que la valeur moyenne, elle descendra la moitié inférieure de l'index et atteindra zéro et ne lancera jamais un index hors des limites. Cependant, si la valeur est supérieure à la valeur moyenne, vous incrémenterez jusqu'à ce que vous atteigniez la dernière valeur, dans ce cas-ci "8", ce qui donnera un index hors limites.

Vous devez être décrémenter votre valeur d'index par un pour tenir compte des indices commençant à 0.

Exemple:

int finalIndex = a.length-1; 

int fruit = searchFruits.length-1;