Mettre en œuvre la recherche

Question

binaire Ceci est mon-recherche binaire:

int binarySearch(int arr[], int value, int min, int max){ 
    int pos = -1; 

    while (max >= min && pos == -1) { 
    int mid = (max+min)/2; 

    if(arr[mid] == value){ 
     pos = mid; 
    }else if(arr[mid] < value){ 
     min = mid +1; 
    }else if(arr[mid] > value){ 
     max = mid -1; 
    } 

    } 
    return pos; 
} 

Je l'appelle ainsi:

//Arr contain values 0-63 
int i = binarySearch(arr, 64, 0, 64); 

Ce sont les valeurs moyennes

32 48 56 60 62 63 64 

Au dernier chèque I essayez d'accéder à un élément à la position 64, lorsque la dernière position dans le tableau est 63.

Quel est le problème avec ma mise en œuvre?

Answer 1

Votre tableau contient des valeurs de 0 -63 (comme vous l'avez mentionné) et vous donnez les valeurs suivantes pour min et max: min = 0, max = 64. Et changez la ligne suivante pour que votre code puisse gérer des valeurs int élevées sinon il y a des chances de dépassement de mémoire.

 int mid = min+(max-min)/2; 

La formule ci-dessus se simplifie en (max + min)/2 lui-même mais de protéger débordement d'entier.

Answer 2

Lorsque max == min, votre longueur est 0, vous ne devriez donc pas entrer dans la boucle. Changer en condition (max > min && ...) si votre haute eau est « un passé la fin » (et votre eau haute devrait probablement être « un après la fin », il est un modèle très utile)

Oh, et le rendre max = mid place de max = mid-1, comme max représente "un au-delà de la fin" plutôt que le dernier élément.

En guise d'amélioration générale du style de codage, lorsque vous faites ce type de code, toss affirme partout que vos index sont dans les limites. Cela peut non seulement détecter les problèmes plus tôt, il peut aussi vous aider à raisonner sur quelles valeurs sont dans les limites et qui ne sont pas ...

Answer 3

essayer

while (max > min && pos == -1) { 
int mid = (max+min)/2; 

if(arr[mid] == value){ 
    pos = mid; 
}else if(arr[mid] < value){ 
    min = mid; 
}else if(arr[mid] > value){ 
    max = mid; 
} 

}