02 — Dichotomie avancée : frontières et recherche sur la réponse

Ce que tu vas apprendre

• Trouver la première position où insérer (borne inférieure et supérieure)
• Pourquoi bisect répond à plus de questions que « est-ce présent »
• La technique de recherche binaire sur l'espace des réponses
• Comment reconnaître un problème « dichotomisable »

Prérequis

• 01 — La recherche dichotomique

La recherche dichotomique de l'article précédent répond à « cet élément est-il présent, et où ? ». Mais la dichotomie résout une classe de problèmes bien plus large. Dès qu'une réponse passe d'un état à un autre de façon monotone (faux, faux, faux, vrai, vrai), on peut trouver la frontière en O(log n). Cette généralisation est l'une des plus utiles de l'algorithmie pratique.

Trouver une frontière, pas une valeur

Souvent, on ne veut pas savoir si une valeur existe, mais où elle se rangerait. C'est la notion de borne inférieure (première position dont l'élément est supérieur ou égal à la cible) et de borne supérieure (première position strictement supérieure). C'est ce que calcule bisect_left et bisect_right en Python.

pythonimport bisect

prix = [10, 20, 20, 20, 30, 40]
bisect.bisect_left(prix, 20)   # 1 : première position d'un 20
bisect.bisect_right(prix, 20)  # 4 : première position après les 20
# nombre de 20 dans la liste : 4 - 1 = 3

La différence entre les deux bornes donne le nombre d'occurrences, en O(log n). Compter les éléments dans une plage [a, b] se fait de même : bisect_right(arr, b) - bisect_left(arr, a). Voici une implémentation de la borne inférieure, qui montre la variante de bornes par rapport à la recherche exacte :

typescript// première position i telle que arr[i] >= cible
function borneInferieure(arr: number[], cible: number): number {
  let bas = 0;
  let haut = arr.length; // noter : length, pas length - 1
  while (bas < haut) {   // noter : <, pas <=
    const milieu = bas + Math.floor((haut - bas) / 2);
    if (arr[milieu] < cible) bas = milieu + 1;
    else haut = milieu; // on garde milieu comme candidat
  }
  return bas;
}

Les bornes diffèrent de la recherche exacte : ici l'intervalle est semi-ouvert [bas, haut), la condition est <, et haut = milieu (pas milieu - 1) parce que le milieu reste un candidat valide. C'est exactement le genre de détail qui justifie de comprendre la dichotomie au lieu de la copier.

La recherche binaire sur la réponse

Voici la généralisation la plus puissante. Parfois, le tableau qu'on dichotomise n'existe même pas : c'est l'espace des réponses possibles. Si tu peux répondre rapidement à la question « une réponse de valeur X est-elle réalisable ? », et que cette réponse est monotone (si X marche, tout X plus grand marche aussi, ou l'inverse), alors tu peux trouver la meilleure réponse par dichotomie.

Exemple concret : tu dois découper un travail en k équipes au maximum, et tu veux minimiser la charge maximale d'une équipe. La charge maximale possible va de « la plus grosse tâche seule » à « toutes les tâches ensemble ». Au lieu de tester toutes les valeurs, tu fais une dichotomie sur la charge maximale autorisée.

pythondef peut_repartir(taches: list[int], k: int, charge_max: int) -> bool:
    equipes, charge_courante = 1, 0
    for t in taches:
        if charge_courante + t > charge_max:
            equipes += 1            # nouvelle équipe
            charge_courante = t
            if equipes > k:
                return False
        else:
            charge_courante += t
    return True

def charge_minimale(taches: list[int], k: int) -> int:
    bas, haut = max(taches), sum(taches)
    while bas < haut:
        milieu = bas + (haut - bas) // 2
        if peut_repartir(taches, k, milieu):
            haut = milieu           # ça marche, on tente plus petit
        else:
            bas = milieu + 1        # trop serré, il faut plus
    return bas

La fonction peut_repartir est en O(n). La dichotomie la rappelle O(log(somme)) fois. Le coût total est O(n log(somme)), bien meilleur que tester chaque valeur en O(n × somme). On a transformé un problème d'optimisation en une suite de questions oui/non, chacune facile.

Reconnaître un problème dichotomisable

Le signal à repérer : la réponse à « X est-il réalisable ? » est monotone. Si X fonctionne, alors tout X au-dessus (ou en dessous) fonctionne aussi. Dès que tu vois cette monotonie, la dichotomie sur la réponse s'applique, même sans tableau trié explicite.

Quelques formulations qui cachent ce pattern :

• « la plus petite valeur telle que… »
• « la capacité minimale pour faire X en au plus K étapes »
• « le plus grand seuil tel qu'une contrainte tient encore »

L'article suivant change de pattern : les deux pointeurs, qui résolvent en O(n) et sans mémoire une autre famille de problèmes sur les tableaux triés.

Sources

• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Chapitre 2. MIT Press.
• Python Software Foundation. bisect — Array bisection algorithm. docs.python.org/3/library/bisect.html
• Halim, S., & Halim, F. (2013). Competitive Programming 3, Section 3.3 "Binary Search the Answer". Lulu. (La technique de recherche sur la réponse)
• Bentley, J. (2000). Programming Pearls (2nd ed.), Colonne 4. Addison-Wesley.