Algo Dichotomie

Identification

Infoforall

4 - Recherche dichotomique


Nous avons vu que parcourir un tableau élément par élément nécessite un algorithme dont le coût est linéaire : sa complexité est Θ(n).

Nous allons voir aujourd'hui comment faire mieux que cela mais sur un tableau particulier : un tableau trié.

Logiciel nécessaire pour l'activité : Python 3 : Thonny, IDLE ou le site repl.it ...

Evaluation ✎ : -

Documents de cours : open document ou pdf

1 - Trier un tableau avec Python

L'opération de tri est fondamentale en informatique.

Lorsqu'on sait qu'on va régulièrement devoir rajouter des données dans un tableau (ou une collection), on doit se demander

  • si on les rajoute simplement à la fin du tableau ou
  • si on s'arrange plutôt pour insérer le nouvel enregistrement directement entre les deux bons enregistrements de façon à avoir un tableau trié.

Commençons par créer un programme générant un tableau aléatoire d'entiers compris entre 0 et 100.

Les deux fonctions qui nous allons vous présenter retournent exactement la même chose mais créent à l'interne le tableau de deux façons différentes :

  • La fonction creer crée un tableau renvoyé par compréhension.
  • La fonction creer2 crée un tableau renvoyé par extension et ajouts successifs (avec la méthode append).

Pour l'utilisateur, c'est totalement transparent : la fonction semble faire la même chose.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
import random def creer(nbr): '''Fonction qui renvoie un tableau de nbr éléments compris entre 0 et 100 :: param nbr(int) :: un entier correspondant au nombre d'éléments voulus :: return (list) :: un tableau d'entiers de nbr éléments compris entre 0 et 100 ''' tableau = [random.randint(0,100) for x in range(nbr)] return tableau def creer2(nbr): '''Fonction qui renvoie un tableau de nbr éléments compris entre 0 et 100 :: param nbr(int) :: un entier correspondant au nombre d'éléments voulus :: return (list) :: un tableau d'entiers de nbr éléments compris entre 0 et 100 ''' tableau = [] for index in range(nbr): tableau.append(random.randint(0,100)) return tableau
>>> creer(5) [81, 78, 52, 42, 25] >>> creer2(5) [73, 62, 88, 69, 81]

01° Tester les deux fonctions dans la Console après avoir mis les fonctions en mémoire. Par exemple en créant des listes de 10 ou 50 éléments.

En tapant help(creer) dans la Console, dire si le créateur de la fonction a clairement précisé la précondition sur l'argument (à savoir qu'on doit envoyer un entier) ?

...CORRECTION...

>>> help(creer) Help on function creer in module __main__: creer(nbr) Fonction qui renvoie un tableau de nbr éléments compris entre 0 et 100 :: param nbr(int) :: un entier correspondant au nombre d'éléments voulus :: return (list) :: un tableau d'entiers de nbr éléments compris entre 0 et 100

Donc, oui, c'est clairement noté qu'on doit fournir un entier.

Il n'empêche que rien n'oblige l'utilisateur à envoyer un entier. Il peut très bien le faire. Mais ça provoque une erreur. Et c'est de sa faute, vous lui aviez dit !

Si on veut stocker le résultat fourni par la fonction, il faudra le stocker dans une variable.

>>> tab1 = creer(5) >>> tab2 = creer2(10) >>> tab1 [11, 34, 31, 56, 88] >>> tab2 [13, 55, 54, 57, 12, 80, 16, 72, 30, 99]
Coût d'un algorithme de recherche linéaire

Nous avions vu que le coût d'une recherche linéaire est en n puisqu'il faut lire les éléments un par un jusqu'à trouver l'élément ou arriver au bout du tableau.

Dans le pire des cas (l'élément cherché n'est pas dans le tableau), on va donc avoir à lire tous les index un par un.

Nous avions écrit que cet algorithme est en Θ(n).

Exemple : cherchons 2 dans [13, 55, 54, 57, 12, 80, 16, 72, 30, 99].

Nous allons devoir lire les 10 éléments : d'abord 13, puis 55, puis 54 ...

Si le tableau contenait 1000 éléments, il aura fallu lire 1000 éléments.

D'où la notion de coût linéaire ou Θ(n) : si le tableau comporte n éléments, l'algorithme aura à faire en gros n étapes dans le pire des cas.

Oui mais... on peut faire mieux. On peut travailler sur un tableau trié. Ce sera plus simple non ?

L'une des activités sur les algorithmes va être de réaliser nous même un tri, pour voir comment on peut faire. Néanmoins, c'est une opération très importante en informatique, tous les langages possèdent une ou des fonctions qui permettent de faire cela de façon efficace.

Nous allons en voir deux avec Python.

1 - Fonction native sorted

La fonction native sorted renvoie une copie triée du tableau transmis à la fonction.

Cela veut dire que le tableau originel n'est pas modifié : il est toujours dans le désordre.

>>> tab_initial = creer2(10) >>> tab_initial [13, 55, 54, 57, 12, 80, 16, 72, 30, 99] >>> tab_trie = sorted(tab_initial) >>> tab_trie [12, 13, 16, 30, 54, 55, 57, 72, 80, 99] >>> tab_initial [13, 55, 54, 57, 12, 80, 16, 72, 30, 99]
  • Avantage : on garde en mémoire la configuration initiale des donnnées
  • Désavantage : ça prend deux fois plus de place mémoire. Avec 96 milliards de données de 4 octets, ça peut être important...
2 - Méthode sort

La méthode sort modifie en place le tableau.

>>> tab_initial = creer2(10) >>> tab_initial [13, 55, 54, 57, 12, 80, 16, 72, 30, 99] >>> tab_initial.sort() >>> tab_initial [12, 13, 16, 30, 54, 55, 57, 72, 80, 99]
  • Avantage : moins de place mémoire nécessaire
  • Désavantage : si on veut retrouver l'état initial, il faut espérer que les données initiales sont stockées ailleurs que dans ce tableau.

02° Utiliser une instruction dans la Console (une des deux façons de faire précédentes) pour obtenir une version triée du tableau ci-dessous. Fournir les instructions et le tableau trié.

tableau = [49, 13, 95, 90, 57, 82, 13, 59, 1, 11, 55, 25, 23, 66, 60, 76, 88, 10, 86, 60, 57, 35, 3, 62, 65, 22, 95, 33, 5, 76, 93, 24, 98, 16, 20, 70, 68, 47, 61, 19, 60, 6, 16, 37, 36, 96, 80, 28, 0, 54, 99, 65, 90, 71, 88, 41, 86, 81, 42, 38, 15, 62, 79, 46, 63, 100, 68, 45, 99, 41, 30, 91, 15, 77, 2, 83, 11, 52, 52, 7, 40, 29, 32, 32, 32, 17, 34, 42, 71, 73, 94, 75, 69, 30, 85, 98, 42, 34, 86, 54]

Le plus beau, c'est que ça fonctionne aussi avec les strings. On peut ainsi trier une liste de mots par ordre alphabétique.

Comment fait-il ? Il regarde simplement la valeur ASCII (ou UNICODE pour les valeurs supérieures à 127) et trie par rapport à cette valeur.

A c'est 65, B c'est 66, a c'est 97.

Ainsi un mot commençant par A passera avant un mot commençant par a.

UNICODE - ord et chr

ASCII est une table de conversion qu'on peut considérer comme un standard. On travaille sur un octet et on dispose donc de valeurs allant de 0 à 255. ASCII n'impose que les associations lettre-valeur sur les caractères de 0 à 127.

UNICODE est lui une simple association entre un nombre et un caractère. Il comporte quasiment tous les glyphes et caractères que l'humanité utilise. On ne préoccupe pas de savoir comment on encode concrétement ce nombre en mémoire. Aucune histoire de 'sur 1 octet', 'sur 4 octets'.

Voyez pour l'instant UNICODE comme une simple association nombre <--> caractère.

Fonction ord

En Python, on peut trouver la valeur UNICODE d'un caractère en utilisant la fonction native ord.

>>> ord('A') 65 >>> ord('B') 66 >>> ord('a') 97 >>> ord('z') 122 >>> ord('ç') 231

Ainsi, lorsque Python doit classer des mots, il place les mots commençant par ç après les mots en z puisque la valeur unicode du ç est supérieure à celle du z !

Fonction chr

C'est l'inverse : on lui donne un caractère et elle renvoie la valeur UNICODE correspondante.

>>> chr(65) 'A' >>> chr(231) 'ç' >>> chr(9821) '♝' >>> chr(9822) '♞' >>> chr(9823) '♟'

03° Utiliser le programme suivant qui

  • Ligne 01 : place une phrase sans ponctuation en mémoire
  • Ligne 03 : utilise l'espace comme caractère séparateur pour créer un tableau contenant donc les mots de la phrase en utilisant la méthode split.
  • Ligne 04 : crée un nouveau tableau trié basé sur le tableau non trié précédent en utilisant la fonction native sorted.
  • Ensuite : affiche les deux tableaux pour les comparer.
1 2 3 4 5 6 7 8 9
phrase_sans_ponctuation = "Voici la phrase qui contient deux fois voici pour montrer que UNICODE ne traite pas de la même façon le V et le v" tableau = phrase_sans_ponctuation.split(' ') tableau_trie = sorted(tableau) print('Tableau initial :') print(tableau) print('\nTableau trié :') print(tableau_trie)

Questions

Pourquoi les mots en V sont-ils devant les mots en v dans le tableau trié ?

Pourquoi le mot "UNICODE" est-il devant le mot "contient" alors qu'on compare U et c ?

Pourquoi V est-il devant Voici ?

...CORRECTION...

Le plus simple pour répondre à cela est d'aller voir les codes UNICODE du V et du v.

>>> ord('V') 86 >>> ord('v') 118

Puisque l'ordinateur classe les caractères en fonction de l'UNICODE, le V va passer devant le v.

De la même façon, la valeur UNICODE du U est plus petite que la valeur UNICODE du c.

Tableau initial ['Voici', 'la', 'phrase', 'qui', 'contient', 'deux', 'fois', 'voici', 'pour', 'montrer', 'que', 'UNICODE', 'ne', 'traite', 'pas', 'de', 'la', 'même', 'façon', 'le', 'V', 'et', 'le', 'v'] Tableau trié : ['UNICODE', 'V', 'Voici', 'contient', 'de', 'deux', 'et', 'façon', 'fois', 'la', 'la', 'le', 'le', 'montrer', 'même', 'ne', 'pas', 'phrase', 'pour', 'que', 'qui', 'traite', 'v', 'voici']

Maintenant que vous savez trier des tableaux de nombres ou de caractères, nous allons voir comment faire des recherches plus rapides que de simples recherches séquentielles.

2 - Principe de la recherche dichotomique

Activité de recherche en débranchée à faire avant si possible.

Un rappel avant de commencer :

Rappel sur le lien entre logarithme 2 d'un entier et nombre de bits de cet entier

Le logarithme base 2 peut être vu comme la réciproque de la fonction exponentielle base 2 :

  • Un algorithme dont le coût est exponentiel, en Θ(2n) par exemple, est un algorithme qui ne sera pas exploitable avec un nombre important de données. Pour n devenant de plus en plus grand, il sera pire que n'importe quel algorithme polynomial en nx
  • Un algorithme dont le coût est logarithmique, en Θ(log2(n)) par exemple, est un algorithme beaucoup plus performant qu'un algorithme linéaire et de n'importe quel algorithme polynomial.

Exemple avec 16 (ou 24)

>>> import math >>> math.log2(16) 4.0 >>> math.log2(2**4) 4.0

On voit donc que log2(16) renvoie 4 car 16 peut s'écrire 24.

On remarque aussi que 1610 s'écrit avec 5 bits en base 2 :  1 0000 

On trouve donc le nombre de bits de 16 en calculant log2(16)+1.

Exemple avec 32 (ou 25)

>>> import math >>> math.log2(32) 5.0 >>> math.log2(2**5) 5.0

On voit donc que log2(32) renvoie 5 car 32 peut s'écrire 25.

On remarque aussi que 3210 s'écrit avec 6 bits en base 2 :  10 0000 

On trouve donc le nombre de bits de 32 en calculant log2(32)+1.

Exemple avec 64 (ou 26)

>>> import math >>> math.log2(64) 6.0 >>> math.log2(2**6) 6.0

On voit donc que log2(64) renvoie 6 car 64 peut s'écrire 26.

On remarque aussi que 6410 s'écrit avec 7 bits en base 2 :  100 0000 

On trouve donc le nombre de bits de 64 en calculant log2(64)+1.

Exemple avec 33 (ou 25+1)

>>> import math >>> math.log2(33) 5.044394119358453 >>> math.log2(2**5+1) 5.044394119358453

On voit donc que log2(33) renvoie un nombre entre 5 et 6 car 25 < 33 < 26.

On remarque aussi que 3310 s'écrit avec 6 bits en base 2 :  10 0001 

On trouve donc le nombre de bits de 33 en prenant l'arrondi inférieur de log2(33)+1.

Généralisation

On peut obtenir le nombre de bits b nécessaire pour encoder un entier naturel n en utilisant la formule suivante :

 b = arrondi inférieur de log2(n) + 1 

Exemple

Combien de bits pour encoder le nombre 1 785 124 000 ?

Facile, il suffit de calculer son log2 et de rajouter 1 !

>>> math.log2(1785124000) 30.73337714559171

Il faut donc 30+1 soit 31 bits pour encoder 1785124000.

Voyons maintenant le fonctionnement de la dichotomie.

La condition de base pour pouvoir réaliser cette recherche est d'avoir un tableau trié.

Cherchons par exemple si  x = 40  est présent dans un tableau trié de 20 éléments (les index sont donc compris entre 0 et 19).

Le tableau est borné par deux valeurs d'index à gauche et à droite :

  1. g valant 0 à gauche (symbolisé par )
  2. d valant 19 à droite (symbolisé par )

La case centrale est donc la case  (0+19)//2 ,  c = 9 .

Index 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

A chaque itération, nous allons "supprimer" la moitié des cases restantes. Comment ?

  • Si la valeur centrale c n'est pas la bonne mais que  t[c] > x 
    • on supprime la zone de droite de la recherche en modifiant la valeur de d :  d = c - 1 
  • Si la valeur centrale c n'est pas la bonne mais que  t[c] < x 
    • on supprime la zone de gauche de la recherche en modifiant la valeur de g :  g = c + 1 

Etape 1 - Intervalle de départ [ 0 ; 19 ] qui contient 20 éléments

  • on considère  g = 0 .
  • on considère  d = 19 .
  • On calcule l'index central à l'aide d'une division entière :  (0+19)//2  donne  9  On aura donc  c = 9 .
  • Comme  t[9] = 60  et donc  t[9] > 40 , on "supprime" la partie droite en modifiant d.
  • On impose donc  d = 9 - 1 = 8 

Index 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

Etape 2 : Intervalle [0 ; 8] qui contient 9 éléments

  • on considère  g = 0 .
  • on considère  d = 8 .
  • On calcule l'index central à l'aide d'une division entière : (0+8)//2 donne 4 On aura donc  c = 4 .
  • Comme  t[4] = 18  et donc  t[4] < 40 , on "supprime" la partie gauche en modifiant g.
  • On impose donc  g = 4 + 1 = 5 

Index 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

Etape 3 : Intervalle [5;8] qui contient 4 éléments

  • on considère  g = 5 .
  • on considère  d = 8 .
  • On calcule l'index central à l'aide d'une division entière : (5+8)//2 donne 6 On aura donc c = 6.
  • Comme  t[6] = 37  et donc  t[6] < 40 , on "supprime" la partie gauche en modifiant g.
  • On impose donc  g = 6 + 1 = 7 

Index 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

Etape 4 : Intervalle [7;8] qui contient 2 éléments

  • on considère  g = 7 .
  • on considère  d = 8 .
  • On calcule l'index central à l'aide d'une division entière : (7+8)//2 donne 7 On aura donc  c = 7 .
  • Comme  t[7] = 59  et donc  t[7] > 40 , on "supprime" la partie droite en modifiant g.
  • On impose donc  d = 7 - 1 = 6 

Index 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

Puisque d < g, il ne reste plus rien à explorer et nous n'avons pas trouvé notre élément.

Conclusion : 40 n'appartient pas à notre tableau.

Réponse obtenue avec 4 comparaisons. C'est mieux que 20 non ?

Si vous voulez revoir la progression de la recherche, voici l'animation globale.

Index 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

04° Réaliser une recherche du nombre 50 dans le tableau à l'aide d'une recherche dichotomique.

Index 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
Elément 18 23 25 35 48 50 58 68 70 73 75 79 80 82 85 89

L'intervalle initiale de l'étape 1 est donc [0;15].

 g = 0  et  d = 15 .

Question :

Rédiger la recherche progressive de 50 dans ce tableau :

    Décrire l'étape 1

  • Que vaut l'index central  c  de l'étape 1 ?
  • Comparer la valeur centrale et la valeur cherchée
  • Modifier g ou d en fonction de la comparaison
  • Passer à l'étape 2

  • ...

...CORRECTION...

En image puis avec les explications :

Index 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
Elément 18 23 25 35 48 50 58 68 70 73 75 79 80 82 85 89

Etape 1

  • on considère  g = 0 .
  • on considère  d = 15 .
  • On calcule l'indice central à l'aide d'une division entière : (0+15)//2 donne 7 On aura donc  c = 7 .
  • Comme  t[7] = 69  et donc  t[7] > 50 , on "supprime" la partie droite en modifiant d.
  • On impose donc  d = 7 - 1 = 6 

Etape 2

  • on considère  g = 0 .
  • on considère  d = 6 .
  • On calcule l'indice central à l'aide d'une division entière : (0+6)//2 donne 3 On aura donc  c = 3 .
  • Comme  t[3] = 35  et donc  t[3] < 50 , on "supprime" la partie gauche en modifiant g.
  • On impose donc  g = 3 + 1 = 4 

Etape 3

  • on considère  g = 4 .
  • on considère  d = 6 .
  • On calcule l'indice central à l'aide d'une division entière : (4+6)//2 donne 5 On aura donc  c = 3 .
  • Comme  t[5] = 50 , on vient de trouver la bonne valeur.

05° Nous avons fait 3 comparaisons pour effectuer cette recherche. Deux questions :

  1. Combien de comparaisons aurait-on dû faire avec une recherche séquentielle ?
  2. Quelle est la condition sur le tableau pour pouvoir effectuer la recherche dichotomique ?
Nombre d'étapes maximales

Puisqu'on divise à chaque fois l'intervalle restant par deux, on peut prévoir le nombre maximale d'étapes dans le pire des cas lorsqu'on effectue une recherche par dichotomie.

Exemple avec un tableau de 16 valeurs (24)

  • on remarque que 16 nécessite 5 bits en binaire  1 0000 

Description de la recherche dans le pire des cas (pas de chance à chaque étape, on tombe du côté où il reste le plus de cases à tester !)

  • Etape 1 : une comparaison sur un ensemble de 16 valeurs : 8 d'un côté, le pilier et 7 de l'autre.
  • Etape 2 : une comparaison sur au pire 8 valeurs : 4 d'un coté, le pilier et 3 de l'autre .
  • Etape 3 : une comparaison sur au pire 4 valeurs : 2 d'un côté, le pilier et 1 de l'autre.
  • Etape 4 : une comparaison sur au pire 2 valeurs : 1 valeur et le pilier.
  • Etape 5 finale avec la comparaison sur la dernière valeur possible.

Conclusion : autant d'étapes que de bits pour encoder le nombre de cases en base 2 : arrondi inférieur de log2(n)+1.

Exemple avec un tableau de 17 valeurs (24 + 1)

  • on remarque que 17 nécessite 5 bits en binaire  1 0001 

Description de la recherche dans le pire des cas (pas de chance à chaque étape, on tombe du côté où il reste le plus de cases à tester !)

  • Etape 1 : une comparaison sur un ensemble de 17 valeurs : 8 d'un côté, le pilier et 8 de l'autre.
  • Etape 2 : une comparaison sur au pire 8 valeurs : 4 d'un coté, le pilier et 3 de l'autre .
  • Etape 3 : une comparaison sur au pire 4 valeurs : 2 d'un côté, le pilier et 1 de l'autre.
  • Etape 4 : une comparaison sur au pire 2 valeurs : 1 valeur et le pilier.
  • Etape 5 finale avec la comparaison sur la dernière valeur possible.

Conclusion : autant d'étapes que de bits pour encoder le nombre de cases en base 2 : arrondi inférieur de log2(n)+1.

Exemple avec un tableau de 31 valeurs

  • on remarque que 31 nécessite 5 bits en binaire  1 1111 

Description de la recherche dans le pire des cas (pas de chance à chaque étape, on tombe du côté où il reste le plus de cases à tester !)

  • Etape 1 : une comparaison sur un ensemble de 31 valeurs : 15 d'un côté, le pilier et 15 de l'autre.
  • Etape 2 : une comparaison sur au pire 15 valeurs : 7 d'un coté, le pilier et 7 de l'autre .
  • Etape 3 : une comparaison sur au pire 7 valeurs : 3 d'un côté, le pilier et 3 de l'autre.
  • Etape 4 : une comparaison sur au pire 3 valeurs : 1 d'un côté, le pilier et 1 de l'autre..
  • Etape 5 finale avec la comparaison sur la dernière valeur possible.

Conclusion : autant d'étapes que de bits pour encoder le nombre de cases en base 2 : arrondi inférieur de log2(n)+1.

Exemple avec un tableau de 32 valeurs

  • on remarque que 32 nécessite 6 bits en binaire  10 0000 
  • Etape 1 : une comparaison sur un ensemble de 32 valeurs.
  • Etape 2 : une comparaison sur au pire 16 valeurs.
  • Etape 3 : une comparaison sur au pire 8 valeurs.
  • Etape 4 : une comparaison sur au pire 4 valeurs.
  • Etape 5 : une comparaison sur au pire 2 valeurs.
  • Etape 6 finale avec la comparaison sur la dernière valeur possible.

Conclusion : autant d'étapes que de bits pour encoder le nombre de cases en base 2 : arrondi inférieur de log2(n)+1.

Généralisation

En utilisant la méthode dichotomique pour chercher une valeur dans un tableau trié de n éléments, on voit que le nombre d'étapes est dans le pire des cas lié à l'arrondi inférieur de log2(n)+1.

Lorsqu'on cherche le coût, on ne recherche qu'à connaître le type d'évolution, et pas l'évolution exacte. On met donc de coté les constantes et autres facteurs multiplicatifs.

L'algortihme de rechercher par dichotomie possède dont un coût logarithmique et on peut écrire que cet algorithme est dans le pire des cas Θ(log2 n).

C'est bien entendu bien mieux que dans le cas de la recherche séquentielle.

A titre d'exemple, sur un tableau d'un million de valeurs,

  • Méthode séquentielle : 1 000 000 de comparaisons dans le pire des cas
  • Méthode dichotomique : log2(1 000 000) + 1 comparaisons, soit 20 comparaisons !

Par contre, n'oubliez pas que le tableau doit être trié.

Si vous voulez vous amuser à prévoir le nombre de coups sur différents exemples, voici un tableau automatisée où vous pouvez créer des valeurs aléatoires et faire une recherche sur une valeur donnée.

Valeur cherchée :

Index 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

3 - Preuve de terminaison

Nous avions montré que la recherche séquentielle s'arrête nécessairement.

Faisons maintenant la même chose avec la recherche dichotomique.

Commençons par présenter l'algorithme maintenant que vous parvenez à l'appliquer.

Algorithme de recherche dichotomique

But : trouver si un élément recherché existe bien dans un tableau. S'il existe, on fournit l'indice de la première occurrence trouvée. Sinon, il renvoie une réponse vide.

Principe : dans un tableau trié, on regarde la valeur centrale dans les indices encore disponibles. S'il ne s'agit pas de la bonne valeur, on enlève de l'intervalle de recherche les indices qui ne peuvent pas contenir la valeur recherchée.

Description des entrées / sortie

  • ENTREES :
    • tableau : un tableau trié contenant un ensemble d'éléments.
    • x : un élément voulu qu'on tente de rechercher dans le tableau
    • (optionnelle selon les langages d'implémentation): longueur, le nombre d'éléments dans le tableau
  • SORTIE : une réponse vide (à définir) ou un nombre correspondant à l'index trouvé.

Algorithme commenté

Dans l'algorithme ci-dessous, l'opérateur // désigne une division entière.

    g ← 0

    dlongueur - 1

    TANT QUE g <= d

      c(g + d) // 2

      SI tableau[c] < x

        on ne garde que ce qui est à droite de l'index centre

        g(c + 1)

      SINON SI tableau[c] > x

        on ne garde que ce qui est à gauche de l'index centre

        d(c - 1)

      SINON

        Si on arrive ici, c'est que x est à l'index centre

        Renvoyer c

      Fin du Si

    Fin Tant que

    Si on arrive ici, c'est que l'intervalle de recherche est vide

    Renvoyer VIDE

Algorithme non commenté

    g ← 0

    dlongueur - 1

    TANT QUE g <= d

      c(g + d) // 2

      SI tableau[c] < x

        g(c + 1)

      SINON SI tableau[c] > x

        d(c - 1)

      SINON

        Renvoyer c

      Fin du Si

    Fin Tant que

    Renvoyer VIDE

Cet algorithme est la traduction directe des actions effectuées dans la partie précédente.

Preuve de terminaison

Pour montrer que l'algorithme se termine, il faut montrer que :

  • ses boucles s'expriment sous la forme while un > 0
  • avec un variant un qui correspond à une suite d'entiers strictement décroissante.

06° Montrer que  TANT QUE g <= d  revient à écrire  TANT QUE longueur > 0 

...CORRECTION...

 TANT QUE g <= d 

 TANT QUE 0 <= ( d - g

 TANT QUE ( d - g ) >= 0 

 TANT QUE ( d - g ) > -1 

 TANT QUE ( d - g + 1) > 0 

Or que vaut justement cette grandeur d - g + 1 ?

Il s'agit de la longueur de l'intervalle qu'on étudie.

Index 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
Elément 18 23 25 35 48 50 58 68 70 73 75 79 80 82 85 89

Comme vous le voyez, prouver la terminaison revient à prouver que longueur décroît strictement à chaque fois qu'on fait un tour de boucle.

Il y a deux cas à traiter :

  1. Le cas où l'intervalle contient un nombre impair d'éléments : longueur vaut 2k+1 = k + 1 + k
  2. Avec k=3 :              

    Avec k=2 :            

    Avec k=1 :          

    Avec k=0 :         

    Dans ce cas, c'est simple : on supprime l'élément central orange et k élements bleus ou rouges, soit k+1 éléments. Du coup :

    longueurN+1 = longueurN - (k+1)

    On supprime donc k+1 éléments.

    Au minimum pour k=0, on supprime donc au moins 1 élément, l'élément central.

  3. Le cas où l'intervalle contient un nombre pair d'éléments : longueur vaut 2k = (k-1) + 1 + k
  4. Avec k=3 :            

    Avec k=2 :          

    Avec k=1 :        

    Cas A : on supprime les éléments rouges, donc k-1 + 1, soit k éléments. Du coup :

    longueurN+1 = longueurN - k

    On réduit bien d'au moins 1 la longueur de l'intervalle puisque k ≥ 1.

    Cas B : on supprime les éléments bleus soit k + 1 éléments. Du coup :

    longueurN+1 = longueurN - (k+1)

    On réduit bien d'au moins 2 la longueur de l'intervalle puisque k ≥ 1.

    Conclusion Cas A ou Cas B : on supprime au moins k éléments à chaque tour de boucle (donc au moins 1 puisque k ≥ 1)

07° En reprenant

  • l'essentiel de la démonstration ci-dessus liée au variant longueurN : il diminue d'au moins un élément à chaque tour de boucle, et
  • le fait qu'on puisse écrire la condition de la boucle non bornée sous la forme TANT QUE longueurN > 0

que pouvez-vous en conclure sur la terminaison de cet algorithme ?

...CORRECTION...

Nous avons d'abord montré que TANT QUE g <= d  revient à écrire  TANT QUE longueur > 0 

Nous avons ensuite montré que le variant longueurN est décroissant.

Or, ce variant est bien un entier puisqu'il correspond aux nombres d'éléments présents dans le sous-tableau de la recherche.

L'algorithme se termine donc dans tous les cas puisque :

  1. sa boucle s'exprime sous la forme while un > 0
  2. avec un variant un qui correspond à une suite d'entiers strictement décroissante.

4 - Python

Il reste à voir comment réaliser cela avec Python.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
import random def creer(nbr): '''Fonction qui renvoie un tableau de nbr éléments compris entre 0 et 100 :: param nbr(int) :: un entier correspondant au nombre d'éléments voulus :: return (list) :: un tableau d'entiers de nbr éléments compris entre 0 et 100 ''' tableau = [random.randint(0,100) for x in range(nbr)] return tableau def recherche_dicho(tableau, x): '''Fonction qui cherche l'élément x dans le tableau trié de façon dichotomique :: param tableau(list) :: un tableau trié d'éléments :: param x (variable) :: l'élément à chercher dans le tableau :: return (NoneType ou int) :: l'index de l'élément ou None .. Précondition 1 :: le tableau ne doit pas être vide .. Précondition 2 :: le tableau doit être TRIE .. Précondition 3 :: x doit être du même type que les éléments du tableau ''' g = 0 d = len(tableau) - 1 while g <= d : print(f"Un tour de boucle avec l'intervalle [{g}; {d}]") c = (g + d) // 2 # Division entière if tableau[c] < x : g = c + 1 elif tableau[c] > x : d = c - 1 else : return c return None # Inutile en réalité : ce serait fait automatiquement if __name__ == '__main__' : tab_test = sorted( creer(100) ) print(tab_test) numero = recherche_dicho(tab_test, 5) print(numero)

08° Utiliser le programme pour voir quelques résultats. Quelle est la ligne qui provoque l'affichage purement pédagogique sur les différents intervalles étudiés lors du déroulement dans la fonction recherche_dicho ?

Voici quelques exemples :

[1, 2, 2, 4, 4, 5, 6, 7, 8, 8, 11, 12, 13, 15, 15, 16, 16, 17, 17, 18, 21, 21, 24, 24, 25, 25, 26, 27, 29, 31, 31, 32, 33, 34, 35, 38, 39, 42, 42, 45, 45, 46, 48, 49, 50, 52, 55, 56, 56, 58, 59, 61, 61, 61, 62, 62, 63, 64, 65, 66, 66, 67, 71, 74, 75, 75, 75, 76, 76, 76, 77, 78, 78, 83, 83, 83, 84, 84, 84, 85, 85, 86, 88, 88, 88, 88, 89, 90, 90, 90, 92, 93, 94, 94, 94, 94, 96, 97, 98, 100] Un tour de boucle avec l'intervalle [0; 99] Un tour de boucle avec l'intervalle [0; 48] Un tour de boucle avec l'intervalle [0; 23] Un tour de boucle avec l'intervalle [0; 10] 5

[0, 0, 1, 1, 2, 2, 3, 5, 6, 7, 7, 10, 12, 14, 16, 16, 17, 18, 18, 18, 19, 21, 23, 26, 26, 26, 29, 29, 31, 34, 34, 36, 37, 37, 38, 39, 41, 41, 42, 42, 43, 44, 44, 45, 45, 45, 46, 46, 47, 49, 50, 50, 51, 52, 52, 53, 54, 60, 60, 60, 66, 66, 68, 68, 70, 71, 71, 72, 73, 73, 74, 74, 75, 75, 78, 79, 80, 81, 82, 83, 85, 86, 86, 87, 88, 88, 89, 89, 89, 90, 90, 92, 93, 93, 95, 98, 99, 99, 100, 100] Un tour de boucle avec l'intervalle [0; 99] Un tour de boucle avec l'intervalle [0; 48] Un tour de boucle avec l'intervalle [0; 23] Un tour de boucle avec l'intervalle [0; 10] Un tour de boucle avec l'intervalle [6; 10] Un tour de boucle avec l'intervalle [6; 7] Un tour de boucle avec l'intervalle [7; 7] 7

5 - FAQ

J'ai également vu O(log2 n). C'est quoi ce truc ?

Il s'agit de la fonction logarithme (ici en base 2).

C'est une fonction extrêmement utile : on peut la voir en première approximation comme la fonction qui renvoie la puissance de 2 permettant d'écrire le nombre.

Quelques exemples avec Python

>>> import math >>> math.log2(1) 0.0

Pourquoi ? Simplement car 1 = 20. On renvoie 0.

>>> math.log2(2) 1.0

Pourquoi ? Simplement car 2 = 21. On renvoie 1.

>>> math.log2(4) 2.0

Pourquoi ? Simplement car 4 = 22. On renvoie 2.

>>> math.log2(8) 3.0

Pourquoi ? Simplement car 8 = 23. On renvoie 3.

Le mieux, c'est que cela fonctionne également avec les valeurs qui ne sont pas une puissance entière de 2 !

>>> math.log2(6) 2.584962500721156

Pourquoi ? Simplement car 6 = 22.584962500721156. On renvoie 2.584962500721156. Si vous avez bien compris l'activité sur les floats, vous devriez comprendre qu'il s'agit certainement d'une valeur approximative.

Il existe un logarithme pour toutes les bases possibles et imaginables.

Le logarithme base 10 donne ainsi log10(1000) = 3 puisque 1000 = 103

Ou encore le logarithme népérien ln qui est en lien avec la fonction exponentielle : ln(20) = 2.995732273553991 car on peut écrire

  • 20 = e2.995732273553991 ou encore
  • 20 = exp(2.995732273553991)

Et c'est lié au fait qu'avec un tableau de 1 million d'éléments, la méthode dichotomique ne prend qu'une vingtaine d'étapes au pire

Oui.

>>> math.log2(1E6) 19.931568569324174

Log et Lg, c'est différent ?

Oui.

Lorsqu'on parle simplement de log, on parle du log dans une base donnée. Si c'est rien n'est précisé, c'est certainement la base 10.

Habituellement, si on note juste log, on parle du log10.

Si on note lg(x), on parle de log2(x) dans un contexte informatique. Cela évite de noter log10(x). On note juste lg(x)

Attention donc au contexte dans lequel apparaît un logarithme.

Log et Ln, c'est différent ?

Oui.

Lorsqu'on parle simplement de log, on parle du log dans une base donnée. Si c'est rien n'est précisé, c'est certainement la base 10.

Lorsqu'on parle de ln, on parle du logarithme népérien en mathématiques. Vous le verrez en terminale.

Sauf que dans les documents informatiques, on parle souvent du logarithmique base 2. On devrait le noter log2 ou log2. Mais souvent, la complexité ou le coût apparaît sous la forme lg (voir au dessous) mais aussi parfois ln. Pourquoi ? Tout simplement car log2(x) = ln (x) / ln (2). ln 2 n'est donc qu'un coefficient multiplicateur. C'est un peu comme un coût en 0.5n3 qu'on noterait juste n3.

Attention donc au contexte dans lequel apparaît un logarithme.

Petit résumé des notations

On voit juste log : c'est certainement log10.

On voit juste lg : c'est certainement log2.

On voit juste ln : c'est le logarithme népérien.

Activité publiée le 05 04 2020
Dernière modification : 14 04 2020
Auteur : ows. h.