Recherche binaire: lower bound, tableau roté, recherche par réponse

1. Vue d’ensemble

La recherche binaire est un algorithme de recherche sur des données triées avec une complexité O(log n). L’idée est très simple, mais l’implémentation est facile à rater : boucle infinie, décalage d’une unité (off-by-one), débordement d’entier lors du calcul de mid.

Cet article progresse de la version basique aux variantes courantes : chercher la première/dernière position d’éléments dupliqués, compter les occurrences, chercher dans un tableau roté, et recherche binaire sur la réponse. Après lecture, vous aurez un ensemble de schémas d’implémentation robustes, accompagnés de tests pour les valider.

2. Recherche binaire basique

Supposons que vous avez un tableau de prix de produits trié en ordre croissant et que vous devez chercher la position d’un prix donné :

public final class PriceSearch {

    public static int search(int[] prices, int target) {
        int lo = 0;
        int hi = prices.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (prices[mid] == target) {
                return mid;
            }
            if (prices[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] prices = {100, 150, 200, 350, 500};
        System.out.println(search(prices, 350));
        System.out.println(search(prices, 300));
    }
}

Explications :

• lo et hi forment un intervalle fermé [lo, hi]. C’est la région où target peut se trouver.
• La condition lo <= hi signifie que la boucle s’exécute tant que l’intervalle contient au moins un élément.
• mid = lo + (hi - lo) / 2 évite les débordements. Écrire (lo + hi) / 2 déborderait quand lo + hi dépasse Integer.MAX_VALUE. Une écriture équivalente est (lo + hi) >>> 1.
• Après chaque itération, on exclut mid de l’intervalle (mid + 1 ou mid - 1), donc l’intervalle se réduit toujours et la boucle se termine.

Résultat :

3
-1

Cette version suffit quand le tableau n’a pas d’éléments dupliqués et que vous voulez juste savoir « existe-t-il ». Avec des éléments dupliqués, elle retourne une position quelconque dans le groupe. Généralement, ce n’est pas ce que vous voulez.

3. Lower bound et upper bound

Les deux variantes les plus importantes sont :

• lower bound : le premier indice où a[i] >= target.
• upper bound : le premier indice où a[i] > target.

Les deux retournent toujours un indice dans [0, n], même si target n’existe pas dans le tableau. Cet indice est précisément la position d’insertion pour garder le tableau trié.

public final class Bounds {

    public static int lowerBound(int[] a, int target) {
        int lo = 0;
        int hi = a.length;              // intervalle semi-ouvert [lo, hi)
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    public static int upperBound(int[] a, int target) {
        int lo = 0;
        int hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] <= target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

Différences par rapport à la version basique :

• On utilise un intervalle semi-ouvert [lo, hi), donc hi est initialisé à a.length et la condition de boucle est lo < hi.
• Quand a[mid] satisfait la condition « assez grand », on pose hi = mid au lieu de mid - 1, car mid peut être la réponse.
• Les deux fonctions ne diffèrent que par les opérateurs < et <=.

Testons avec un tableau ayant des éléments dupliqués :

int[] prices = {100, 200, 200, 200, 350, 500};
System.out.println(Bounds.lowerBound(prices, 200)); // 1
System.out.println(Bounds.upperBound(prices, 200)); // 4
System.out.println(Bounds.lowerBound(prices, 300)); // 4
System.out.println(Bounds.lowerBound(prices, 900)); // 6

1
4
4
6

Avec 300, le résultat 4 dit que si on insère 300, il viendrait avant 350. Avec 900, le résultat est n, ce qui signifie tous les éléments sont plus petits.

3.1. Première position, dernière position et nombre d’occurrences

À partir de ces deux fonctions, vous déduisez immédiatement les problèmes courants :

public static int firstIndexOf(int[] a, int target) {
    int i = Bounds.lowerBound(a, target);
    return (i < a.length && a[i] == target) ? i : -1;
}

public static int lastIndexOf(int[] a, int target) {
    int i = Bounds.upperBound(a, target) - 1;
    return (i >= 0 && a[i] == target) ? i : -1;
}

public static int count(int[] a, int target) {
    return Bounds.upperBound(a, target) - Bounds.lowerBound(a, target);
}

Avec le tableau prices ci-dessus et target = 200, on obtient firstIndexOf = 1, lastIndexOf = 3, count = 3. Règle à retenir : toujours vérifier les limites i < a.length (ou i >= 0) avant de lire a[i].

3.2. Compter les éléments dans une plage

Une application pratique : compter le nombre de commandes avec un total dans [min, max] :

public static int countInRange(int[] sortedTotals, int min, int max) {
    return Bounds.upperBound(sortedTotals, max) - Bounds.lowerBound(sortedTotals, min);
}

Avec {100, 200, 200, 200, 350, 500} et la plage [150, 400], le résultat est 5 - 1 = 4. Chaque requête ne coûte que O(log n), sans parcourir le tableau entier.

4. Recherche dans un tableau roté

Un tableau roté est un tableau trié qu’on « coupe » à un point et dont on échange les deux moitiés, par exemple {40, 50, 60, 10, 20, 30}. Le tableau n’est plus croissant globalement, mais au moins une moitié autour de mid reste ordonnée. On s’en sert pour décider de la direction :

public static int searchRotated(int[] a, int target) {
    int lo = 0;
    int hi = a.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        if (a[mid] == target) {
            return mid;
        }
        if (a[lo] <= a[mid]) {                 // la moitié gauche est ordonnée
            if (a[lo] <= target && target < a[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } else {                               // la moitié droite est ordonnée
            if (a[mid] < target && target <= a[hi]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return -1;
}

Explications :

• a[lo] <= a[mid] indique que l’intervalle [lo, mid] est croissant. Si target est dans la plage de valeurs de cet intervalle, on rétrécit à gauche. Sinon, on va à droite.
• Sinon, l’intervalle [mid, hi] est croissant, et on raisonne de façon symétrique.

System.out.println(searchRotated(new int[]{40, 50, 60, 10, 20, 30}, 20));
System.out.println(searchRotated(new int[]{40, 50, 60, 10, 20, 30}, 45));

4
-1

Attention : Cette implémentation suppose que le tableau n’a pas d’éléments dupliqués. Avec un tableau comme {2, 2, 2, 3, 2}, la condition a[lo] <= a[mid] ne peut plus distinguer quelle moitié est ordonnée. Dans ce cas, il faut gérer le cas a[lo] == a[mid] en incrémentant lo d’une unité, et la complexité dans le pire cas devient O(n).

5. Recherche binaire sur la réponse

C’est la variante la plus puissante. Elle ne cherche pas dans un tableau mais trouve la plus petite valeur satisfaisant une condition. La seule condition pour l’appliquer est que le prédicat soit monotone : si x la satisfait, alors tous les nombres supérieurs à x la satisfont aussi. Autrement dit, la suite de résultats a la forme false, false, ..., true, true.

Écrivons une fonction générique :

import java.util.function.LongPredicate;

public final class AnswerSearch {

    /** La plus petite valeur dans [lo, hi] où ok retourne true. Suppose ok(hi) == true. */
    public static long firstTrue(long lo, long hi, LongPredicate ok) {
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (ok.test(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

Cette fonction a la même structure que lowerBound. En fait, lowerBound n’est qu’un cas particulier avec le prédicat a[i] >= target.

Application à un problème réel : l’entrepôt a une liste de colis dans un ordre fixe, qui doivent être livrés en maxDays jours. Chaque jour, le camion transporte des colis consécutifs, avec un poids total ne dépassant pas la capacité du camion. Quelle est la capacité minimale ?

import java.util.Arrays;

public final class ShippingPlanner {

    public static long minCapacity(int[] weights, int maxDays) {
        long lo = Arrays.stream(weights).max().orElse(0);
        long hi = Arrays.stream(weights).asLongStream().sum();
        return AnswerSearch.firstTrue(lo, hi, cap -> canShip(weights, maxDays, cap));
    }

    static boolean canShip(int[] weights, int maxDays, long capacity) {
        int days = 1;
        long load = 0;
        for (int w : weights) {
            if (load + w > capacity) {
                days++;
                load = 0;
            }
            load += w;
        }
        return days <= maxDays;
    }

    public static void main(String[] args) {
        System.out.println(minCapacity(new int[]{3, 2, 2, 4, 1, 4}, 3));
    }
}

Explications :

• lo est le colis le plus lourd, car le camion doit pouvoir transporter au moins un colis quelconque. hi est le poids total, car une seule journée suffirait. Donc ok(hi) est toujours vrai.
• canShip simule une stratégie gloutonne : on charge des colis jusqu’à dépasser la capacité, puis on passe au jour suivant. Plus la capacité est grande, moins de jours il faut, donc le prédicat est monotone.
• Le coût total est O(n · log(sum)), au lieu d’essayer chaque capacité.

6

Avec une capacité de 6, l’horaire de livraison est [3, 2], [2, 4], [1, 4], exactement 3 jours. Avec une capacité de 5, il faudrait 4 jours, donc 5 ne convient pas.

Le même schéma résout de nombreux autres problèmes : le nombre minimum de threads pour traiter les batchs à temps, le débit minimum à respecter, la racine carrée entière d’un nombre.

6. Utiliser la bibliothèque standard de Java

Java a déjà Arrays.binarySearch et Collections.binarySearch. Vous devez comprendre la valeur qu’elles retournent :

int[] prices = {100, 200, 200, 200, 350, 500};
System.out.println(Arrays.binarySearch(prices, 350));
System.out.println(Arrays.binarySearch(prices, 300));

4
-5

• Si l’élément est trouvé, la fonction retourne l’indice de l’élément.
• Si pas trouvé, la fonction retourne -(insertionPoint) - 1. Ici la position d’insertion est 4, donc le résultat est -5. Pour récupérer la position d’insertion, calculez -(result) - 1.
• Avec des éléments dupliqués, la documentation ne garantit pas de retourner une position particulière du groupe. Si vous avez besoin de la première ou dernière position, utilisez votre propre implémentation de lowerBound/upperBound.

Avec une liste d’objets, passez un Comparator cohérent avec l’ordre du tri :

record Order(String id, long total) {}

List<Order> orders = List.of(
        new Order("A1", 120), new Order("B7", 300), new Order("C3", 450));
int idx = Collections.binarySearch(
        orders, new Order("?", 300), Comparator.comparingLong(Order::total));
System.out.println(idx); // 1

Attention : Collections.binarySearch sur LinkedList n’atteint pas O(log n) car accéder par indice coûte O(n). Utilisez ArrayList ou un tableau.

7. Tests

Ajoutez les dépendances JUnit 5 et AssertJ. Si votre projet utilise spring-boot-starter-test, les deux sont déjà inclus.

<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>5.11.0</version>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.assertj</groupId>
    <artifactId>assertj-core</artifactId>
    <version>3.26.3</version>
    <scope>test</scope>
</dependency>

Écrivez des tests pour les cas limites. C’est là que la recherche binaire se casse le plus souvent :

import org.junit.jupiter.api.Test;
import java.util.Random;
import java.util.stream.IntStream;
import static org.assertj.core.api.Assertions.assertThat;

class BoundsTest {

    private final int[] prices = {100, 200, 200, 200, 350, 500};

    @Test
    void lowerAndUpperBoundHandleDuplicates() {
        assertThat(Bounds.lowerBound(prices, 200)).isEqualTo(1);
        assertThat(Bounds.upperBound(prices, 200)).isEqualTo(4);
    }

    @Test
    void boundsReturnInsertionPointAtEdges() {
        assertThat(Bounds.lowerBound(prices, 50)).isZero();
        assertThat(Bounds.lowerBound(prices, 900)).isEqualTo(prices.length);
        assertThat(Bounds.lowerBound(new int[0], 1)).isZero();
    }

    @Test
    void lowerBoundMatchesLinearScan() {
        Random random = new Random(42);
        for (int round = 0; round < 1_000; round++) {
            int[] a = random.ints(random.nextInt(20), 0, 10).sorted().toArray();
            int target = random.nextInt(12) - 1;
            int expected = (int) IntStream.of(a).filter(x -> x < target).count();
            assertThat(Bounds.lowerBound(a, target)).isEqualTo(expected);
        }
    }

    @Test
    void minCapacityFindsSmallestFeasibleValue() {
        int[] weights = {3, 2, 2, 4, 1, 4};
        assertThat(ShippingPlanner.minCapacity(weights, 3)).isEqualTo(6);
        assertThat(ShippingPlanner.canShip(weights, 3, 5)).isFalse();
    }
}

Le test lowerBoundMatchesLinearScan compare avec le comptage linéaire sur 1000 tableaux aléatoires, y compris les vides. Ce type de test de concordance attrape les erreurs off-by-one bien mieux que quelques exemples écrits à la main.

8. Erreurs courantes et quand ne pas l’utiliser

Erreurs fréquentes :

• Mélanger les conventions d’intervalle. Vous initialisez hi = n (semi-ouvert) mais bouclez while (lo <= hi) et posez hi = mid - 1. Vous lisez alors hors du tableau. Choisissez une convention et restez-y cohérent.
• Boucle infinie. Si vous écrivez lo = mid avec mid = (lo + hi) / 2, quand hi = lo + 1 alors mid == lo et l’intervalle ne rétrécit pas. Si vous avez vraiment besoin de lo = mid, arrondissez vers le haut : mid = lo + (hi - lo + 1) / 2.
• Débordement d’entier au calcul de mid ou quand on somme dans une recherche binaire sur la réponse. Utilisez long pour les valeurs qui peuvent être grandes.
• Prédicat non monotone. La recherche binaire retourne un nombre, mais ce nombre n’a pas de sens. Prouvez la monotonie avant d’appliquer.

Quand ne pas utiliser la recherche binaire :

• Les données ne sont pas triées et vous cherchez seulement quelques fois. Trier coûte O(n log n), mais une recherche linéaire coûte O(n).
• Vous cherchez juste « oui ou non » avec plusieurs recherches. Un HashSet donne O(1) en moyenne.
• Les données changent souvent, avec beaucoup d’insertions et suppressions. Garder un tableau trié coûte O(n) par insertion. Envisagez TreeMap/TreeSet, qui ont déjà ceilingKey, floorKey, higherKey équivalant aux lower et upper bounds.
• Le tableau est très petit, quelques dizaines d’éléments. Un parcours linéaire est souvent plus rapide grâce au cache, et le code est plus simple.

9. Conclusion

La recherche binaire n’est pas juste « trouver un élément dans un tableau ». Quand on maîtrise le lower bound et l’upper bound avec l’intervalle semi-ouvert [lo, hi), on résout les problèmes de première/dernière position, de comptage dans une plage, en quelques lignes. Un tableau roté demande une étape supplémentaire pour identifier la moitié ordonnée. La recherche binaire sur la réponse étend la technique à tous les problèmes avec un prédicat monotone.

Gardez une convention d’intervalle unique, utilisez >>> ou lo + (hi - lo) / 2 pour éviter les débordements, et ayez toujours un test de concordance avec un parcours linéaire. Ces trois habitudes éliminent la plupart des bugs pour lesquels la recherche binaire est réputée difficile.