Recherche binaire accédant à un index hors plage

Question

Voici le code :

char binarySearch(unsigned int target, int* primes, unsigned int size){
    int* ptrToArray = primes;
    unsigned int first = 0;
    unsigned int last = size;

    while (first <= last){
        unsigned int middle = first + (last - first) / 2;
        printf("first: %d, last: %d, middle: %d\n", first, last , middle);

        if (ptrToArray[middle] == target){
            return 1;
        }

        if (ptrToArray[middle] < target){
            first = middle + 1;
        }else{
            last = middle - 1;
        }
    }
    return 0;
}

Voici le résultat :

J'ai regardé ce bout de code pendant plus d'une heure et je n'arrive toujours pas à trouver où est la faille.

Answer 1

Si middle es 0 Si vous n'êtes pas en mesure de le faire, l'instruction

last = middle - 1

provoque un débordement d'entier ; les conditions doivent être légèrement modifiées.

Answer 2

Le problème est que vous définissez vos variables d'index ( first , last , middle ) comme unsigned int dans votre logique, last peut en effet devenir négatif. Mais dans ce cas, puisqu'ils sont définis comme unsigned et en raison de la façon dont fonctionne la représentation en complément à 2 des nombres négatifs, la condition dans votre while est toujours d'actualité.

Regardez l'exemple de code suivant pour l'illustrer :

#include <stdio.h>

int main() {
  /* defining the variables as unsigned */
  unsigned int first_u = 0;
  unsigned int last_u = -1;

  if (first_u <= last_u)
    printf("less than\n");
  else
    printf("greater or equal\n");

  /* defining the variables as signed */
  int first_s = 0;
  int last_s = -1;

  if (first_s <= last_s)
    printf("less than\n");
  else
    printf("greater or equal\n");

  return 0;
}

Pour le reste, vous devez utiliser soit < dans votre while -ou définir la valeur initiale de last comme size-1 . Sinon, si vous recherchez un élément qui est plus grand que le dernier élément de votre tableau, vous sortirez des limites.

Answer 3

Tout d'abord, la valeur négative du milieu est due à un dépassement de capacité (unsigned int).

Je pense aussi que vous devriez avoir : unsigned int last = size-1 parce que si first devient égal à last=size, vous utiliserez ptrToArray[middle] et middle=size donc il sera en dehors des limites du tableau. Cela résoudra également le cas de taille =0 mentionné ci-dessus.

Enfin, pour rendre votre code plus lisible, vous pouvez écrire : middle =(first+last)/2 qui est le milieu de l'espace [premier, dernier], et equals to first+(last-first)/2 .