Searching: linear and binary
Deux façons de chercher
- Chercher signifie trouver où se trouve une valeur dans un tableau (ou dire qu'elle n'y est pas).
- La recherche linéaire vérifie chaque élément un par un. Elle fonctionne sur n'importe quel tableau.
- La recherche binaire est beaucoup plus rapide mais nécessite que le tableau soit trié au préalable.
Recherche linéaire
- Parcourez de l'index
0àn - 1, en comparant chaque élément à la cible. - Retournez l'index dès que vous le trouvez. Si vous arrivez à la fin, retournez
-1. - Pour un tableau de
néléments, cela examine jusqu'ànd'entre eux.
Pourquoi le tri permet la recherche binaire
- Si le tableau est trié, vous pouvez sauter au milieu et comparer.
- Si le milieu est trop petit, la cible doit être dans la moitié droite ; si trop grand, dans la moitié gauche.
- Chaque étape élimine la moitié du tableau, donc c'est très rapide (environ
log2(n)étapes).
low, high, mid
- Gardez deux bornes :
low(début) ethigh(fin). Le milieu estmid = low + (high - low) / 2. - Si
a[mid]est la cible, retournezmid. Sia[mid] < target, déplacezlow = mid + 1; sinonhigh = mid - 1. - Arrêtez quand
low > high— la cible n'est pas là, donc retournez-1.
#include <stdio.h>
int main(void) {
int a[] = {1, 3, 5, 7, 9}; // sorted!
int target = 7, lo = 0, hi = 4, found = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) { found = mid; break; }
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
printf("%d\n", found); // 3
return 0;
}
Erreurs courantes
- La recherche binaire nécessite un tableau trié.
- La recherche linéaire vérifie chaque élément à son tour.
À vous maintenant
- Pour la recherche binaire, supposez que le tableau est déjà trié. Utilisez
low,high, etmid. - Retournez
-1quand la valeur n'est pas trouvée. Ne writez pas demain— le vérificateur en fournit un.
Recherche linéaire vs binaire
Binary search halves the range each step.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
Complete int linear_search(const int a[], int n, int target) so it returns the index of the first target, or -1 if it is not in the array. Do non write a main.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
Complete int binary_search(const int a[], int n, int target) for a sorted array. Return the index of target, or -1. Use low, high, and mid. Do non write a main.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
Complete int first_negative(const int a[], int n) so it returns the index of the first item less than 0, or -1 if there is none. Do non write a main.
Cliquez sur Exécuter pour voir le résultat ici.