C++ Girl
  1. C++ Girl
  3. Pourquoi écrivons-nous lo + (hi-lo) / 2 en recherche binary?
Intereting Posts
Comment vérifier si une tâche std :: async est terminée? Qu’advient-il d’un pointeur déréférencé dans l’instruction return? Stroustrup ppp chapitre 8 têtes de forage Obtenir un pointeur partagé à partir d’une valeur déréférencée d’un pointeur partagé J’aimerais utiliser le curseur span de Qxt sans avoir à l’installer. Est-ce possible? Icône de la barre d’état système en C ++ ifstream ouvrir le fichier C ++ Pourquoi l’ajout d’une boucle d’enregistrement supplémentaire fait-il une grande différence sur certaines machines et une petite différence sur d’autres? cin.peek pour la validation des entrées Les exceptions doivent-elles être chaînées en C ++? Quel est l’intérêt de iter_swap? Le compilateur ac / c ++ optimise-t-il les divisions constantes par la puissance de deux en décalages? Accéder à l’opérateur à partir d’un pointeur Pointeurs de caractère et pointeurs entiers (++) cin.eof () et feof (stdin) sont discordants

Pourquoi écrivons-nous lo + (hi-lo) / 2 en recherche binary?

Je lisais à propos de la recherche binary … Je sais que la méthode traditionnelle de recherche de valeur moyenne est la suivante: 

mid=(hi+lo)/2

Mais je vois aussi que pour éviter le débordement, la valeur moyenne est calculée comme ça 

 mid=lo+(hi-lo)/2

Mais pourquoi?? Je ne pouvais pas trouver la raison réelle … Est-ce que quelqu’un peut me donner la raison avec exemple? C’est différent d’une autre question parce que d’autres questions n’avaient pas la réponse que je voulais avec exemple …

Supposons que vous cherchiez un tableau de 4000000000 éléments en utilisant un unsigned int 32 bits en tant qu’index.

La première étape donnait l’impression que l’élément recherché, s’il était présent, figurerait dans la moitié supérieure. La valeur de lo est 2000000000 et celle de hi est 4000000000 .

hi + lo déborde et produit une valeur inférieure au 6000000000 prévu. Il produit réellement 6000000000-2 32 . En conséquence, (hi + lo) / 2 est une petite valeur. Ce n’est même pas entre lo et hi !

A partir de là, la recherche sera fausse (il sera probablement conclu que l’élément est absent même s’il était présent).

En revanche, même avec les valeurs extrêmes de cet exemple, lo + (hi - lo) / 2 calcule toujours un indice situé à mi-chemin entre hi et lo , comme prévu par l’algorithme.

Mathématiquement, ils sont équivalents.

En termes informatiques, mid=(hi+lo)/2 a moins d’opérations, mais mid=lo+(hi-lo)/2 est préférable pour éviter les débordements.

Supposons que l’élément que vous recherchez se trouve à la fin du tableau, puis hi+lo une 2*size presque égale à 2*size . Puisque la size peut être presque aussi grande que votre index maximum, une 2*size et donc hi+lo peut déborder.