recherche binaire moyen de calcul de valeur de

Voici le pseudo-code que j'ai obtenu à partir d'un TopCoder tutoriel sur la recherche binaire

binary_search(A, target):
   lo = 1, hi = size(A)
   while lo <= hi:
      mid = lo + (hi-lo)/2
      if A[mid] == target:
         return mid            
      else if A[mid] < target: 
         lo = mid+1
      else:
         hi = mid-1

   //target was not found

Pourquoi nous calculons la valeur moyenne, comme mi = lo + (hi - lo) /2 ? Quoi de mal avec (hi + lo) /2

J'ai une légère idée qu'il peut être pour éviter les débordements, mais je ne suis pas sûr, peut-être quelqu'un peut-il m'expliquer et si il y a d'autres raisons derrière tout cela.

InformationsquelleAutor binsearch | 2010-12-26
  1. 20

    Oui, (hi + lo) /2 peut déborder. Ce fut un réel bug de Java binaire de recherche, de mise en œuvre.

    Non, il n'y a pas d'autres raisons pour cela.

    InformationsquelleAutor zeuxcg
  2. 17

    Bien que cette question est de 5 ans, mais il y a un excellent article googleblog qui explique le problème et la solution en détail qui vaut la peine de partager.

    Il est nécessaire de mentionner qu'en l'état actuel de la mise en œuvre d'une recherche binaire dans Java mid = lo + (hi - lo) /2 calcul n'est pas utilisé, à la place la plus rapide et la plus claire de remplacement est utilisé avec zéro remplissez décalage à droite de l'opérateur

    int mid = (low + high) >>> 1;

    • Pour n'importe quel langage de programmation avec des unsigned décalage à droite soutenu, c'est la bonne façon d'aller.
    • À l'aide de zéro remplissez décalage à droite de l'opérateur n'est certainement pas plus clair. Plus performant, oui, mais pas plus clair. Cette optimisation doit être faite par le compilateur, de ne pas le coder.
    InformationsquelleAutor vtor
  3. 11

    De plus tard dans le même tutoriel:

    "Vous pouvez aussi vous demander pourquoi le milieu est calculé en utilisant la mi = lo + (hi-lo)/2 au lieu de l'habituel milieu = (lo+hi)/2. C'est pour éviter un autre potentiel d'arrondi bug: dans le premier cas, nous voulons que la division de toujours arrondir à la baisse, vers la limite inférieure. Mais la division tronque, de sorte que lorsque lo+hi serait négative, il serait de commencer l'arrondi vers la limite supérieure. Le codage le calcul de cette façon, assure que le nombre divisé est toujours positif et donc arrondit toujours comme nous le souhaitons. Bien que le bug n'a pas de surface lorsque l'espace de recherche se compose uniquement d'entiers positifs ou des nombres réels, j'ai décidé de code de cette façon tout au long de l'article pour plus de cohérence."

    InformationsquelleAutor Abhijeet Kashnia
  4. 6

    Il est en effet possible pour (hi+lo) un débordement d'entier. Dans la version améliorée, il peut sembler que la soustraction lo hi et puis l'ajouter à nouveau est inutile, mais il y a une raison: l'exécution de cette opération n'aura pas de débordement d'entier et il en résulte un certain nombre avec le même la parité comme hi+lo, de sorte que le reste de (hi+lo)/2 sera le même que (hi-lo)/2. lo peut ensuite être ajouté sans risque après la division d'arriver au même résultat.

    InformationsquelleAutor Jeremy Elbourn