Très souvent, les programmeurs, même les débutants,face au fait qu'il existe un ensemble de chiffres dans lequel vous devez trouver un certain nombre. Cette collection est appelée un tableau. Et pour y trouver l'élément souhaité, il existe une grande variété de façons. Mais le plus simple d'entre eux peut à juste titre être considéré comme une recherche binaire. Quelle est la méthode donnée? Et comment implémenter la recherche binaire? Pascal est l'environnement le plus simple pour organiser un tel programme, nous allons donc l'utiliser pour étudier.
Tout d'abord, nous examinerons les avantages de cette méthode, car nous pouvons comprendre
Alors, quel est le principe de cetteméthode? Il convient de dire tout de suite que la recherche binaire ne fonctionne dans aucun tableau, mais uniquement dans un ensemble de nombres triés. À chaque étape suivante, l'élément central du tableau est pris (c'est-à-dire par le numéro de l'élément). Si le nombre souhaité est supérieur à la moyenne, alors tout ce qui se trouve à gauche, c'est-à-dire moins que l'élément du milieu, peut être rejeté et ne pas y être recherché. Inversement, si moins que la moyenne - parmi ces chiffres à droite, vous ne pouvez pas rechercher. Ensuite, nous sélectionnons une nouvelle zone de recherche, où le premier élément sera l'élément central de l'ensemble du tableau, et le dernier restera le dernier. Le nombre moyen de la nouvelle région sera ¼ du segment entier, c'est-à-dire (le dernier élément + l'élément central de l'ensemble du tableau) / 2. Encore une fois, la même opération est effectuée - comparaison avec le nombre moyen de la matrice. Si la valeur souhaitée est inférieure à la moyenne, nous rejetons le côté droit et faisons de même plus loin jusqu'à ce que cet élément du milieu soit trouvé.
Bien sûr, il est préférable de regarder un exemple de la façon dont la recherche binaire est écrite. Pascal convient à tout le monde ici - la version n'est pas importante. Écrivons un programme simple.
Il aura un tableau de 1 à h appelé"massiv", une variable indiquant la limite inférieure de la recherche nommée "niz", la limite supérieure appelée "verh", l'élément central de la recherche est "sredn"; et le nombre que vous recherchez isk.
Donc, nous attribuons d'abord les limites supérieure et inférieure de l'intervalle de recherche:
en bas: = 1;
verh: = h + 1;
Ensuite, nous organisons le cycle "alors que le bas est inférieur à la limite supérieure":
Alors que niz
A chaque étape, on divise le segment par 2 :
sredn: = (niz + verh) div 2; {utiliser la fonction div parce que nous divisons sans reste}
Chaque fois que nous vérifions. Si la moyenne est égale à celle souhaitée, on interrompt le cycle, puisque l'élément souhaité a déjà été trouvé:
іf sredn = isk then break;
Si l'élément central du tableau est plus grand que celui souhaité, nous rejetons le côté gauche, c'est-à-dire que nous affectons l'élément central à la limite supérieure:
if massiv [sredn]> isk alors verh: = sredn;
Et si au contraire, alors on en fait la limite inférieure :
sinon niz: = sredn;
fin;
C'est tout ce qui sera au programme.
Voyons à quoi ressemblera la méthode binaire dans la pratique. Prenons un tableau comme celui-ci : 1, 3, 5, 7, 10, 12, 18 et recherchons le nombre 12 qu'il contient.
Au total, nous avons 7 éléments, donc le milieu sera le quatrième, sa valeur est 7.
| 1 | 3 | 5 | 7 | 10 | 12 | 18 |
Étant donné que 12 est supérieur à 7, nous pouvons supprimer les éléments 1,3 et 5. Ensuite, il nous reste 4 nombres, 4/2 sans reste est 2. Ainsi, le nouvel élément du milieu sera 10.
| 7 | 10 | 12 | 18 |
Ici, l'élément du milieu est déjà 12, c'est le nombre souhaité. Tâche terminée - numéro 12 trouvé.
