Searching: linear and binary · Recherche : linéaire et binaire
Two ways to search
- Searching means finding where a value is in an array (or saying it is not there).
- Linear search checks every item one by one. It works on any array.
- Binary search is much faster but needs the array to be sorted first.
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.
Linear search
- Walk from index
0ton - 1, comparing each item to the target. - Return the index the moment you find it. If you reach the end, return
-1. - For an array of
nitems, this looks at up tonof them.
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.
Why sorting enables binary search
- If the array is sorted, you can jump to the middle and compare.
- If the middle is too small, the target must be in the right half; if too big, the left half.
- Each step throws away half the array, so it is very fast (about
log2(n)steps).
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
- Keep two bounds:
low(start) andhigh(end). The middle ismid = low + (high - low) / 2. - If
a[mid]is the target, returnmid. Ifa[mid] < target, movelow = mid + 1; elsehigh = mid - 1. - Stop when
low > high— the target is not there, so return-1.
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;
}
Common mistakes
- Binary search needs a sorted array.
- Linear search checks each element in turn.
Erreurs courantes
- La recherche binaire nécessite un tableau trié.
- La recherche linéaire vérifie chaque élément à son tour.
Now you try
- For binary search, assume the array is already sorted. Use
low,high, andmid. - Return
-1when the value is not found. Do not write amain— the checker provides one.
À 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.
Linear vs binary search · Recherche linéaire vs binaire
Binary search halves the range each step. · La recherche binaire divise la plage par deux à chaque étape.
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 not · non write a main. · Complétez int linear_search(const int a[], int n, int target) pour qu'il retourne l'index du premier target, ou -1 s'il n'est pas dans le tableau. Ne pas écrire de main.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
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 not · non write a main. · Complétez int binary_search(const int a[], int n, int target) pour un tableau trié. Retournez l'index de target, ou -1. Utilisez low, high, et mid. Ne pas écrire de main.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
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 not · non write a main. · Complétez int first_negative(const int a[], int n) pour qu'il retourne l'index du premier élément inférieur à 0, ou -1 s'il n'y en a pas. Ne pas écrire de main.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.