interpolation recherche tableau hors limites

Je crée un programme Java qui utilise la recherche d'interpolation ci-dessous que j'ai obtenu de wikipedia. Dans mon programme principal, j'ai créé un tableau int qui aura 100 000 spots. Ensuite, je remplis tous ces spots avec des nombres aléatoires et je les trier. Je génère ensuite une clé de recherche aléatoire et appelle la fonction. Je boucle également l'appel de fonction 100 fois chaque fois avec une clé de recherche différente. Lorsque je fais cela, je reçois un tableau hors limites erreur sur cette déclaration if (sortedArray [mid] < toFind). Le programme fonctionne très bien avec un tableau avec 10 spots, 100 spots, 1000 spots, mais quand j'arrive à 100.000, j'ai l'erreur. Savez-vous ce que je peux faire pour résoudre ce problème?interpolation recherche tableau hors limites

public int interpolationSearch(int[] sortedArray, int toFind){ 
    // Returns index of toFind in sortedArray, or -1 if not found 
    int low = 0; 
    int high = sortedArray.length - 1; 
    int mid; 

    while (sortedArray[low] <= toFind && sortedArray[high] >= toFind) { 
    mid = low + 
     ((toFind - sortedArray[low]) * (high - low))/
     (sortedArray[high] - sortedArray[low]); 

    if (sortedArray[mid] < toFind) 
    low = mid + 1; 
    else if (sortedArray[mid] > toFind) 
    // Repetition of the comparison code is forced by syntax limitations. 
    high = mid - 1; 
    else 
    return mid; 
    } 

    if (sortedArray[low] == toFind) 
    return low; 
    else 
    return -1; // Not found 
}

Source

2012-10-06 Joe24

Vous devez vous connecter si mid est toujours supérieur à la longueur du tableau et voir quelles sont les valeurs de low, high et toFind lorsque cela se produit. Ajoutez ceci juste avant l'instruction if. –

Lorsque j'ajoute mid = Math.min (mid, sortedArray.length) juste avant if (sortedArray [mid] Joe24

Vous débordez de la valeur maximale pouvant être stockée dans un int qui est 2 147 483 647.

Lorsque vous calculez le numérateur dans votre équation, vous faites ((39258-0) * (99999-0)) qui est 3 925 760 742.

Si vous changez à cela, vous aurez pas ce problème:

long numerator = (long)(toFind - sortedArray[low]) * (long)(high - low); 
mid = low + numerator/(sortedArray[high] - sortedArray[low]);

Je pense que vous avez aussi besoin de changer votre boucle while être:

while (sortedArray[low] < toFind && sortedArray[high] >= toFind) {

Sinon, vous avez une situation où sortedArray [faible] == sortedArray [haut] == tofind

Ensuite, votre équation se réduit à

mid = low + (0 * (high - low))/0 = 0/0

Java permet la division par zéro. Je ne suis pas exactement sûr de ce qui se passe, il se peut que dans ce cas, mid = infinity ou NaN.

Source

2012-10-06 02:30:29

dois-je ajouter que lorsque mid est déclaré ex: int mid = Math.min (mid, sortedArray.length) ou dans la boucle while au lieu de mid = low + ((toFind - sortedArray [faible]) * (haut - bas))/ (sortedArray [high] - sortedArray [faible]); ? – Joe24

Merci pour votre aide. Je faisais les maths et j'avais une clé de recherche = 39258, low = 0, high = 99999, sortedArray [low] = 0 et sortedArray [high] = 99998. Quand je fais les maths pour la boucle while ça devrait être 0 + ((39258-0) * (99999-0))/(99998 - 0) = 39258. Le programme me dit que cela équivaut à -3692 et que c'est hors limites. Une idée de pourquoi cela se passe? – Joe24

Yep utilise des longs ou des doubles plutôt que des ints. Vous débordez de la taille maximale d'un int. –

Vous devriez développer un code comme celui-ci dans un EDI comme Eclipse (il y en a d'autres). Dans Eclipse, vous pouvez déboguer ce programme et demander au débogueur de s'arrêter chaque fois qu'une exception particulière (Like ArrayOutOfBoundsException) est levée. Vous pouvez ensuite voir quelle ligne de code a provoqué l'erreur et vous pouvez voir la valeur de chaque variable. Avec cette information, il sera beaucoup plus facile d'identifier et de résoudre le problème.

Source

2012-10-06 02:26:09

interpolation recherche tableau hors limites

Répondre

Questions connexes