Comment puis-je simplifier ce code de recherche binary en C?

Hé les gars ont commencé à programmer en C il y a quelques semaines pour apprendre les algorithmes, demandez-vous simplement comment rendre mon code plus simple. Mais la seule chose à faire est de garder les arguments identiques, merci d’avance.

bool search(int value, int values[], int n) { int min = values[0]; int max = values[n-1]; int average = (min + max) / 2; if(average == value) { return true; } while (average > value) { max = average - 1; average = (min + max) / 2; } while (average < value) { min = average + 1; average = (min + max) / 2; } if (max < min) { return false; } if (average == value) { printf("%i\n", average); return true; } else { return false; } } 

Ceci n’est pas une bonne implémentation de la recherche binary, toutes les conditions doivent être dans une boucle, telles que: Max doit être égal à n-1 et non aux valeurs [n-1] et min = 0 au lieu des valeurs [0], comme il se doit comparer les valeurs [moyenne] avec la valeur et pas seulement la variable moyenne.

  bool search(int value, int values[], int n){ int min = 0; int max = n-1; int average ; while(max>=min){ average = (min + max) / 2; if(values[average] == value) { return true; } if (values[average] > value) { max = average - 1; average = (min + max) / 2; } if (values[average] < value) { min = average + 1; average = (min + max) / 2; } } return false; } 

Il y a un tas de petites choses que vous devez obtenir correctement dans une recherche binary: gérer la longueur = 0 cas, assurez-vous que la position que vous testez est toujours valide, assurez-vous de ne pas déborder (par exemple, `(low + high) / 2 ‘n’est pas le meilleur moyen d’écrire cela), assurez-vous que la nouvelle position de test est toujours différente de la précédente, etc.

Après l’avoir fait un million de fois, chaque recherche binary que j’écris est maintenant effectuée comme ceci:

 bool search(int[] array, int length, int valueToFind) { int pos=0; int limit=length; while(pos>1); if (array[testpos] 

Notez que nous n'avons besoin que d'une comparaison par itération, ce qui est plus rapide que la plupart des implémentations possibles. 2. Au lieu d'effectuer le test d'égalité dans la boucle, nous trouvons de manière fiable la position à laquelle appartient l'élément à rechercher itération, puis à la fin du test pour voir si l'élément que nous voulons est là.

La façon dont nous calculons testpos garantit que pos < = testpos < limit , ET cela fonctionne même si length est la plus grande valeur entière possible.

Ce formulaire facilite également la lecture des invariants que vous voulez voir, sans avoir à penser à des conditions aux limites étranges telles que high . Lorsque vous sortez de la boucle, pos==limit afin que vous n'ayez pas à vous soucier d'utiliser le mauvais, etc.

La condition de cette boucle est également facilement adaptable à des recherches binarys à des fins différentes, telles que "trouver où insérer x, en veillant à ce qu'elle se trouve après tous les x déjà présents dans le tableau", "trouve le premier x du tableau", " trouver le dernier x du tableau ", etc.