Rechercher
La recherche est le processus consistant à déterminer si un élément spécifique existe et sa position exacte dans un ensemble de données. C'est une opération fondamentale impliquée dans presque tous les programmes.
Comparaison de trois algorithmes de recherche
Recherche linéaire O(n)
Ne nécessite pas de données triées
Comparer un par un, simple et fiable
Convient pour : petits ensembles de données ou ensembles non ordonnés
Recherche binaire O(log n)
Nécessite des données triées
Divise la plage par deux à chaque fois, éliminant la moitié
Adapté à : solution généraliste pour des données triées
Recherche par interpolation O(log log n)
Nécessite un ordre trié + une distribution uniforme
Estime la position en fonction de la proportion de la valeur
Adapté à : optimal lorsque les données sont uniformément distribuées
Recherche linéaire
Compare un par un en partant du premier élément jusqu'à ce que la cible soit trouvée ou que la liste soit épuisée. Ne nécessite pas que les données soient triées. Complexité temporelle O(n).
Recherche binaire
Nécessite que les données soient triées. À chaque fois, compare avec l'élément du milieu, réduisant la plage de recherche de moitié. Complexité temporelle O(log n).
Recherche par interpolation
Une optimisation de la recherche binaire. Au lieu de prendre le point médian, elle estime la position possible en fonction de la valeur cible. Lorsque les données sont uniformément réparties, elle peut atteindre O(log log n).
Exemple
/* Recherche linéaire : O(n), ne nécessite pas d'ordre trié */
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) return i;
}
return -1;
}
/* Recherche binaire : O(log n), nécessite que le tableau soit trié (ordre croissant) */
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2; /* Calcul évitant le dépassement de capacité */
if (arr[mid] == target) return mid; /* Trouvé */
if (arr[mid] < target)
left = mid + 1; /* La cible est dans la moitié droite */
else
right = mid - 1; /* La cible est dans la moitié gauche */
}
return -1; /* Non trouvé */
}
/* Recherche par interpolation : O(log log n) en moyenne, nécessite des données uniformément distribuées */
int interpolationSearch(int arr[], int n, int target) {
int low = 0, high = n - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
/* Formule d'interpolation : estimer la position en fonction de la taille proportionnelle de la valeur */
int pos = low + ((target - arr[low]) * (high - low))
/ (arr[high] - arr[low]);
if (arr[pos] == target) return pos;
if (arr[pos] < target)
low = pos + 1;
else
high = pos - 1;
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
int n = 9;
printf("Recherche linéaire 50 : indice %d"\n", linearSearch(arr, n, 50)); /* Sortie : 4 */
printf("Recherche binaire 50 : indice %d"\n", binarySearch(arr, 0, n-1, 50)); /* Sortie : 4 */
printf("Recherche par interpolation 50 : indice %d"\n", interpolationSearch(arr, n, 50)); /* Sortie : 4 */
return 0;
}
Résumé comparatif des complexités
| Algorithme | Complexité temporelle | Nécessite des données triées | Scénarios applicables |
|---|---|---|---|
| Recherche linéaire | O(n) | non | Petit volume de données ou non triées |
| Recherche binaire | O(log n) | Oui | Tableaux triés, généraux et efficaces |
| Recherche par interpolation | O(log log n)Moyenne | Oui | Scénarios spécifiques avec des données uniformément distribuées |