Recherche de tableau linéaire
Très souvent, vous devez trouver une valeur donnée dans un tableau ou signaler qu'elle n'y est pas. Pour ce faire, vous devez parcourir tous les éléments du tableau du premier au dernier. Dès qu'un élément égal à la valeur donnée X est trouvé, la recherche doit se terminer et le résultat doit s'afficher. Un tel algorithme est appelé linéaire.
Un algorithme linéaire est utilisé pour trouver l'élément maximum (minimum) d'un tableau. C'est aussi un algorithme de recherche. Mais ici on est obligé d'aller au bout du tableau, car il est nécessaire de comparer tous les éléments avec la valeur maximale (minimale) actuelle et si l'élément actuel est supérieur (inférieur) à la valeur maximale (minimale), remplacer la valeur maximale (minimale).
|
Une autre approche pour résoudre ce problème est possible. Vous pouvez utiliser une sortie anticipée de la boucle si la valeur requise est trouvée.
En C++, l'instruction break est utilisée pour sortir d'une boucle ;
|
Recherche binaire
La recherche binaire (ou binaire) est un algorithme de recherche efficace et plus rapide que la recherche linéaire. Par exemple, pour un tableau de 1024 éléments, une recherche linéaire dans le pire des cas (lorsque l'élément recherché n'est pas dans le tableau) traitera les 1024 éléments, mais il suffit de traiter 10 éléments avec une recherche binaire. Ce résultat est obtenu grâce au fait qu'après la première étape de la boucle, la zone de recherche se réduit à 512 éléments, après la seconde – jusqu'à 256 etc.
Les inconvénients de cet algorithme sont la nécessité d'ordonner les données, ainsi que la possibilité d'accéder à n'importe quel élément de données dans un temps constant (indépendant de la quantité de données). Par conséquent, l'algorithme ne peut pas fonctionner sur des tableaux non ordonnés.
Algorithme
- Sélectionnez l'élément intermédiaire
A[c] et comparez avec X.
- Si
X = A[c] alors trouvé (stop).
- Si
X < A[c], chercher plus loin dans la première moitié.
- Si
X > A[c], regardez plus loin dans la seconde moitié.
Mise en œuvre
L = 0 ; R=N; // segment initial
tandis que ( L < R - 1)
{
c = (L + R) / 2 ; // a trouvé le milieu
if ( X < A[c] ) // compression de segment
R=c;
autre
L = c ;
}
si ( A[L] == X)
cout << "A" << L<< "]=" << X;
autre
cout << "Introuvable";
où :
A - tableau source,
N - taille du tableau,
X - numéro recherché,
D'autres implémentations sont possibles.
Par exemple, en utilisant une sortie anticipée de la boucle
L = 0 ; R = N-1 ;
tandis que (R >= L)
{
c = (L + R) / 2 ;
si ( X == A[c] )
{
nX = c ;
casser;
}
si (X < ; A[c]) R = milieu - 1 ;
si (X > A[c]) L = milieu + 1 ;
}
si ( nX < 0)
cout << "Non trouvé";
autre
cout << "A" << nX<< "]=" << X ;
|
Comparaison des algorithmes de recherche linéaire et binaire par le nombre de comparaisons
Exemples
| # |
Recherche de ligne |
Recherche binaire |
| 2 |
2 |
2 |
| 16 |
16 |
5 |
| 1024 |
1024 |
11 |
| 1048576 |
1048576 |
21 |
L'avantage du tri binaire est qu'il est plus rapide.
Inconvénients : un tableau pré-trié est nécessaire.
|