La recherche dichotomique

La condition qui autorise à éliminer une moitié

Le tableau doit être trié dans l’ordre croissant. Si sa valeur centrale est inférieure à la cible, toutes les valeurs placées à gauche sont également trop petites. On peut donc éliminer cette partie sans lire chaque case. Si la valeur centrale est supérieure, on élimine la partie droite. Sans tri, cette déduction serait fausse.

La dichotomie peut renvoyer un indice ou signaler l’absence. Dans la version étudiée, plusieurs occurrences égales peuvent conduire à n’importe laquelle d’entre elles. Trouver spécialement la première occurrence demanderait une adaptation ; ce n’est pas une garantie implicite de la recherche.

La déduction élimine des indices grâce à l’ordre des valeurs. Si le milieu contient 17 et la cible vaut 21, toute case d’indice inférieur ou égal au milieu contient au plus 17 et ne peut convenir. On n’affirme pas que ces valeurs sont inconnues ou inutiles en général : elles deviennent impossibles pour cette cible précise. Chaque déplacement de borne doit pouvoir se justifier par cette implication.

Définir précisément les bornes

Nous utilisons deux indices inclusifs g et d : toutes les cases de g à d sont encore candidates. Initialement, g vaut 0 et d vaut n - 1. Le milieu est la partie entière de (g + d) / 2. Si la cible est plus grande que t[m], la nouvelle borne gauche vaut m + 1, puisque la case centrale a déjà été écartée.

Si la cible est plus petite, d devient m - 1. Quand g dépasse d, l’intervalle ne contient plus de case. Ce n’est pas une anomalie : c’est la situation normale permettant de conclure que la cible est absente.

def dichotomie(t, cible):
    g, d = 0, len(t) - 1
    while g <= d:
        m = (g + d) // 2
        if t[m] == cible:
            return m
        if t[m] < cible:
            g = m + 1
        else:
            d = m - 1
    return -1

Un intervalle qui rétrécit vraiment

Tant que la boucle continue, le nombre de cases candidates est d - g + 1. Ce nombre entier positif diminue strictement après chaque comparaison non concluante. Il constitue un variant de boucle : la recherche ne peut donc pas continuer indéfiniment. Écrire g = m pourrait empêcher cette diminution lorsque le milieu est déjà égal à g.

La propriété conservée est différente : si la cible apparaît dans le tableau, une occurrence reste dans la zone candidate tant qu’elle n’a pas été trouvée. La terminaison prouve l’arrêt ; cette propriété explique pourquoi une moitié peut être éliminée sans perdre une solution.

Au départ d’un tableau vide, g=0 et d=-1. La condition de boucle est fausse avant le moindre accès, et le résultat est -1. Sur un singleton, une seule visite décide soit du succès, soit de l’intervalle vide. Ces cas sont courts à dérouler et particulièrement efficaces pour repérer les erreurs sur < et <=.

Mesurer la réduction plutôt que réciter une formule

Après une étape, il reste environ la moitié des cases, puis le quart, puis le huitième. Pour 16 valeurs, cette version effectue au plus 5 visites de milieu, selon la cible et les arrondis. Pour un tableau non vide de taille n, cette borne est la partie entière de log₂(n) plus 1.

Le coût est logarithmique en nombre de visites. Il suppose notamment un accès direct aux cases. Trier au préalable un tableau uniquement pour une recherche ajoute un coût qu’il ne faut pas oublier. La comparaison avec une recherche séquentielle dépend donc du contexte et du nombre de recherches à effectuer.

Deux recherches proches, deux conclusions différentes

Sur [2,5,8,12], cherchons 8. Les bornes initiales sont 0 et 3, donc le milieu vaut 1 et contient 5. On garde les indices 2 à 3 ; le milieu vaut 2 et l’égalité donne le résultat 2. Cherchons maintenant 9 : les deux premières visites sont identiques, mais 8 est trop petit. Les bornes deviennent 3 et 3 ; on visite 12, puis la borne droite devient 2. La zone est vide.

Ces traces montrent qu’une case restante doit encore être visitée. Utiliser une boucle strictement g < d sans traitement final du singleton peut manquer une cible. Pour contrôler votre tableau, notez les bornes avant la visite, le milieu et la décision. Les bornes suivantes doivent exclure exactement la partie démontrée impossible, y compris le milieu lorsqu’il n’est pas égal à la cible.

Choisir la méthode selon le contexte

Si un tableau de mesures non triées ne sera interrogé qu’une fois, une recherche séquentielle peut suffire. Trier puis chercher ajoute un traitement préalable et peut modifier l’ordre des données. Si un catalogue trié reçoit de nombreuses requêtes, on peut au contraire exploiter son ordre à chaque recherche. Le coût total dépend donc de la préparation, du nombre de requêtes et des éventuelles mises à jour.

Le résultat standard n’est pas forcément la première occurrence. Dans [1,4,4,4,9], la première visite peut trouver l’indice 2 alors que le premier 4 est à l’indice 1. C’est correct si le contrat demande une occurrence quelconque. Trouver la première demande de conserver un résultat provisoire et de poursuivre vers la gauche, ce qui constitue une variante à spécifier. Ne corrigez pas un programme qui respecte son contrat en lui attribuant une exigence absente de l’énoncé.

De la compréhension à l’autonomie

À vous de résoudre

Cherchez d’abord par vous-même. Vérifiez les résultats demandés, utilisez les indices si nécessaire, puis comparez votre méthode à la correction.

Les erreurs qui méritent un détour

Utiliser des bornes inclusives avec une condition prévue pour des bornes exclusives.

Choisissez une convention et gardez-la dans l’initialisation, le test et les mises à jour.

Confondre variant et invariant.

Le variant diminue pour prouver l’arrêt ; l’invariant reste vrai pour justifier le résultat.

Cette notion au bac

Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.

• Bac 2025 · Centres étrangers groupe 1 · Jour 2 : Dictionnaire de mots : hachage, insertion ordonnée et dichotomie

Le prochain pas

• Prouver la correction et la terminaison d’un algorithme
• Comprendre le coût d’un algorithme
• Arbres binaires de recherche : rechercher et insérer

Retrouver le catalogue de Première

Ce chapitre s’appuie sur le programme officiel de Première (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.