Searching: linear and binary · ⁨Recherche : linéaire et binaire⁩ — Java for AP CS A

English

Finding a value

A common job is to search: is a value in an array, and where?
The usual answer is the index where we found it, or -1 if it is not there.
We learn two ways: linear search (works on any array) and binary search (needs a sorted array, but is much faster).

Français

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 -1 si 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).

English

Linear search

Look at each item from index 0 to the end.
If the item equals the target, return its index right away.
If the loop finishes with no match, return -1.

Français

Recherche linéaire

Regarder chaque élément de l'index 0 jusqu'à 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
    }
}

English

How fast is linear search?

In the worst case (the value is last, or missing) it checks every item.
For a list of n items that is up to n checks. We call this linear time.
For small arrays this is totally fine. For huge sorted arrays we can do better.

Français

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'à n vé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.

English

Binary search needs a sorted array

Binary search only works when the array is already sorted (small to large).
It checks the middle item, then throws away half the array each step.
That is much faster: a million items take about 20 checks, not a million.

Français

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.

English

The binary search idea

Keep two bounds: low (start) and high (end).
Look at the middle index mid = (low + high) / 2.
If a[mid] equals the target, return mid.
If a[mid] is too small, the target must be on the right, so set low = mid + 1.
If a[mid] is too big, the target must be on the left, so set high = mid - 1.
Stop when low passes high; then the value is not there, return -1.

Français

L'idée de la recherche binaire

Garder deux bornes : low (début) et high (fin).
Regarder l'index central mid = (low + high) / 2.
Si a[mid] égale la cible, retourner mid.
Si a[mid] est trop petit, la cible doit être à droite, donc définir low = mid + 1.
Si a[mid] est trop grand, la cible doit être à gauche, donc définir high = mid - 1.
Arrêter quand low dépasse high ; 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
    }
}

English

When a value is missing

Both searches return -1 when the target is not in the array.
For binary search, the loop ends when low > high — the bounds have crossed, so there is nowhere left to look.
Always handle the -1 case in code that calls a search.

Français

Quand une valeur est absente

Les deux recherches retournent -1 quand 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 -1 dans 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
    }
}

English

Common mistakes

Binary search needs a sorted array.
Linear search is O(n); binary is O(log n).

Français

Erreurs courantes

La recherche binaire nécessite un tableau trié.
La recherche linéaire est O(n) ; la binaire est O(log n).

English

Now you try

Each task pre-fills the class skeleton — write your code inside main, or complete the method shown.
Press Run to compile and run, then Check answer.
Your code compiles and runs on the server, so even the first run is fast.

Français

À vous maintenant

Chaque tâche préremplit le squelette de classe — écrivez votre code dans main, ou complétez la méthode montrée.
Appuyez sur Exécuter pour compiler et exécuter, puis sur Vérifier la réponse.
Votre code compile et s'exécute sur le serveur, donc même la première exécution est rapide.

Explore · ⁨Explorer⁩

Linear vs binary search · ⁨Recherche linéaire vs binaire⁩

Binary search halves the range each step — far fewer checks. · ⁨La recherche binaire divise la plage par deux à chaque étape — beaucoup moins de vérifications.⁩

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. · ⁨Complétez linearSearch(int[] a, int target). Retournez l'indice du premier élément égal à target, ou -1 s'il n'est pas dans le tableau. Vérifiez les éléments à partir de l'indice 0 vers le haut.⁩

public class SearchUtil {
    // Return the index of target, or -1 if not found.
    public static int linearSearch(int[] a, int target) {
        return -1;   // change this
    }
}

Click Run to see the output here. · ⁨Cliquez sur Exécuter pour voir le résultat ici.⁩

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. · ⁨Complétez binarySearch(int[] a, int target) pour un tableau trié. Utilisez les bornes low/high et vérifiez le milieu à chaque étape. Retournez l'index de target, ou -1 s'il est absent.⁩

public class SearchUtil {
    // Binary search on a sorted array. Return index or -1.
    public static int binarySearch(int[] a, int target) {
        int low = 0;
        int high = a.length - 1;
        // your loop here
        return -1;
    }
}

Click Run to see the output here. · ⁨Cliquez sur Exécuter pour voir le résultat ici.⁩

Complete countOccurrences(int[] a, int target) that returns how many times target appears in a (a linear scan). Return 0 if it never appears. · ⁨Complétez countOccurrences(int[] a, int target) qui retourne combien de fois target apparaît dans a (une balayage linéaire). Retournez 0 s'il n'apparaît jamais.⁩

public class SearchUtil {
    // Count how many times target appears in a.
    public static int countOccurrences(int[] a, int target) {
        return 0;   // change this
    }
}

Click Run to see the output here. · ⁨Cliquez sur Exécuter pour voir le résultat ici.⁩

Searching: linear and binary · ⁨Recherche : linéaire et binaire⁩

Finding a value

Trouver une valeur

Linear search

Recherche linéaire

How fast is linear search?

Quelle est la vitesse de la recherche linéaire ?

Binary search needs a sorted array

La recherche binaire nécessite un tableau trié

The binary search idea

L'idée de la recherche binaire

When a value is missing

Quand une valeur est absente

Common mistakes

Erreurs courantes

Now you try

À vous maintenant

Linear vs binary search · ⁨Recherche linéaire vs binaire⁩

Handout · ⁨Fiche de cours⁩

Log in or create account · ⁨Se connecter ou créer un compte⁩

Your subject · ⁨Votre matière⁩

All sections · ⁨Toutes les sections⁩

Feedback & help · ⁨Retours & aide⁩