Les tableaux en C - Recherche binaire

Précédent ◈ Suivant

rappelez-vous jouer le jeu « Devinez un numéro ». où les réponses à l'énoncé « Je pense à un nombre compris entre 1 et 100 » sont « trop élevé », « trop bas », ou « You Got It! »? Une stratégie qui est souvent utilisée lors de la lecture de ce jeu est de diviser les intervalles entre la conjecture et les extrémités de la plage dans la moitié. Cette stratégie vous aide à affiner rapidement le nombre désiré.

Lors de la recherche d'un tableau, le processus de recherche binaire utilise ce même concept d'intervalles de séparation en deux comme un moyen de trouver la valeur « clé » le plus rapidement possible.

Si votre tableau est dans l'ordre (croissant ou décroissant), vous pouvez rechercher l'élément de votre choix « clé » rapidement en utilisant un algorithme de recherche binaire (appelée l'approche « diviser pour régner »).

Considérez le tableau suivant des entiers:

Tableau d'entiers, num nommé. disposé dans « l'ordre croissant ».

Nous allons recherchons le numéro de clé 64. Voici comment la recherche binaire fonctionnera:

Tout d'abord, le milieu de la matrice se trouve en ajoutant l'indice de matrice de la première valeur de l'indice de la dernière valeur et en divisant par deux: (0 + 9) / 2 = 4 La division entière est utilisée pour arriver à la quatrième indice comme le milieu. (Le milieu mathématique réelle serait entre les 4 et 5 indices, mais nous devons travailler avec entiers indices.)
  • 4 Subscript détient le numéro 45, qui vient avant 64. Nous savons maintenant que 64 existerait dans la partie du tableau à droite de 45. Nous trouvons maintenant au milieu de la partie droite du tableau en utilisant la même approche: ( 5 + 9) / 2 = 7
  • 7 Subscript détient le numéro 73, qui vient après 64 ans, donc nous avons besoin maintenant de trouver le milieu de la partie du tableau à droite de 45, mais à la gauche de 73: (5 + 6) / 2 = 5

  • 5 Subscript détient le numéro 55, qui vient avant 64, donc nous raffinons maintenant à nouveau
    (6 + 6) / 2 = 6 et de l'élément 6 contient le nombre 64.













    • // appel de fonction à la fonction de recherche binaire (voir la liste ci-dessous)
    // pour le tableau ci-dessus
    binarySearch (num, 0, 9, 64);

    // Recherche binaire Fonction
    / Fonction accepte un tableau, les indices liés limite inférieure et supérieure.
    // à fouiller, et le numéro de clé pour lequel nous recherchons.
    // Il n'y a rien retourné.
    binarySearch vide (apvector -tableau, int limiteinf, int limitesup clé int)
    la position int;
    int comparisonCount = 1; // compter le nombre de comparaisons (en option)

    // Pour commencer, trouver l'indice de la position médiane.
    position = (limiteinf + limitesup) / 2;







    Articles Liés

    Précédent ◈ Suivant