Searching: linear and binary
Trouver une valeur
- Une tâche courante est la recherche : une valeur existe-t-elle dans un tableau, et où ?
- La réponse habituelle est l'index où nous l'avons trouvée, ou
-1si elle n'y est pas. - Nous apprenons deux méthodes : recherche linéaire (fonctionne sur tout tableau) et recherche binaire (nécessite un tableau trié, mais est beaucoup plus rapide).
Recherche linéaire
- Regarder chaque élément de l'index
0jusqu'à la fin. - Si l'élément correspond à la cible, retourner son index immédiatement.
- Si la boucle se termine sans correspondance, retourner
-1.
public class Main {
public static void main(String[] args) {
int[] a = {4, 8, 15, 16, 23};
int target = 15;
int found = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] == target) {
found = i;
break; // stop early, we have it
}
}
System.out.println(found); // 2
}
}
Quelle est la vitesse de la recherche linéaire ?
- Dans le cas pire (la valeur est en dernier ou absente), il vérifie chaque élément.
- Pour une liste de
néléments, cela prend jusqu'ànvérifications. On appelle cela une complexité linéaire. - Pour les petits tableaux, c'est tout à fait acceptable. Pour les grands tableaux triés, nous pouvons faire mieux.
La recherche binaire nécessite un tableau trié
- La recherche binaire ne fonctionne que lorsque le tableau est déjà trié (du plus petit au plus grand).
- Elle vérifie l'élément central, puis élimine moitié du tableau à chaque étape.
- C'est beaucoup plus rapide : un million d'éléments prennent environ 20 vérifications, pas un million.
L'idée de la recherche binaire
- Garder deux bornes :
low(début) ethigh(fin). - Regarder l'index central
mid = (low + high) / 2. - Si
a[mid]égale la cible, retournermid. - Si
a[mid]est trop petit, la cible doit être à droite, donc définirlow = mid + 1. - Si
a[mid]est trop grand, la cible doit être à gauche, donc définirhigh = mid - 1. - Arrêter quand
lowdépassehigh; alors la valeur n'est pas là, retourner-1.
public class Main {
public static void main(String[] args) {
int[] a = {2, 5, 8, 12, 16, 23, 38}; // sorted!
int target = 16;
int low = 0;
int high = a.length - 1;
int found = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == target) {
found = mid;
break;
} else if (a[mid] < target) {
low = mid + 1; // go right
} else {
high = mid - 1; // go left
}
}
System.out.println(found); // 4
}
}
Quand une valeur est absente
- Les deux recherches retournent
-1quand la cible n'est pas dans le tableau. - Pour la recherche binaire, la boucle s'arrête quand
low > high— les bornes se sont croisées, il n'y a plus de place à regarder. - Gérer toujours le cas
-1dans le code qui appelle une recherche.
public class Main {
public static void main(String[] args) {
int[] a = {2, 5, 8, 12}; // sorted
int target = 7; // not in the array
int low = 0;
int high = a.length - 1;
int found = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == target) {
found = mid;
break;
} else if (a[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
System.out.println(found); // -1
}
}
Erreurs courantes
- La recherche binaire nécessite un tableau trié.
- La recherche linéaire est O(n) ; la binaire est O(log n).
À vous maintenant
- Chaque tâche préremplit le squelette de classe — écrivez votre code dans main, ou complétez la méthode montrée.
- Utilisez Vérifier la réponse pour compiler votre code avec les tests fournis et voir les résultats. Conservez les interfaces de classe et de méthode montrées dans l'en-tête.
- Votre code compile et s'exécute sur le serveur, donc même la première exécution est rapide.
Recherche linéaire vs binaire
Binary search halves the range each step — far fewer checks.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
Complete linearSearch(int[] a, int target). Return the index of the first item equal to target, or -1 if it is not in the array. Check items from index 0 upward.
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 binarySearch(int[] a, int target) for a sorted array. Use low/high bounds and check the middle each step. Return the index of target, or -1 if it is missing.
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 countOccurrences(int[] a, int target) that returns how many times target appears in a (a linear scan). Return 0 if it never appears.
Cliquez sur Exécuter pour voir le résultat ici.