A partir de Java - Unité 6 tableaux - 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 le tableau qui contient vos données dans l'ordre (croissant ou décroissant), vous pouvez rechercher l'élément clé beaucoup plus rapidement à l'aide d'un algorithme de recherche binaire ( « diviser et conquérir »).

Considérez le tableau suivant des entiers:

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

Nous allons la recherche de l'entier 77:

Tout d'abord, pour le milieu du réseau 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 division entière est utilisée pour arriver à la quatrième indice comme la milieu. (Le milieu mathématique réelle serait entre les 4ème et 5ème subscripts mais nous devons travailler avec entiers indices.)
  • Le 4 détient l'entier indice 52, qui vient avant 77. Nous savons que 77 sera dans cette partie du tableau à droite de 52. Nous trouvons maintenant au milieu de la partie droite du tableau en utilisant la même approche. (5 + 9) / 2 = 7
  • Le 7 détient l'entier indice 89, qui vient après 77. trouver maintenant au milieu de la partie du tableau à droite de 52, mais à la gauche de 89. (5 + 6) / 2 = 5

  • Le 5 détient l'entier indice 63, qui vient avant 77, donc nous avons de nouveau subdivisent
    (6 + 6) / 2 = 6 et le sixième indice détient le nombre entier 77.

    • Rappelez-vous: Vous devez commencer par un tableau pré-triés.

    import java.io. *;
    importation BreezyGUI *.

    BinarySearchExample public class
    public static void main (String [] args)
    clé int = 77;
    int [] num = new int [10];
    // Remplir le tableau
    pour (int i = 0; i < 10; i++)
    num [i] = Console.readInt ( "Entrez entier:");
    // La méthode de recherche binaire
    binarySearch (num, 0, 9, clé);
    >

    méthode de recherche binaire:
    binarySearch (num, 0, 9, clé);

    Les arguments / paramètres sont les suivants:
    tableau - le nom d'un tableau trié
    limiteinf - indice (indice) du premier
    élément de recherche, tableau [0]
    limitesup - indice (index) de
    dernier élément de recherche, tableau [9]
    clé. point nous voulons trouver.

    // Recherche binaire Méthode
    // Cette méthode accepte un tableau prétriés, l'indice de l'élément de départ pour la recherche,
    // l'indice de l'élément de fin de la recherche,
    // et le numéro de clé pour que nous recherchons.
    public static void binarySearch (tableau int [], int limiteinf, int limitesup, clé int)
    la position int;
    int comparisonCount = 1; // comptage du 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