Algo Dichotomie

Identification

Infoforall

3 - 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 ✎ : questions 02-05-08

1 - Trier un tableau avec Python

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

En réalité, lorsqu'on sait qu'on va régulièrement devoir rajouter des données dans un tableau, on doit se demander si on les rajoute simplement à la fin du fichier ou si on s'arrange plutôt pour insérer le nouvel enregistrement entre les deux bons enregistrements de façon à avoir une collection triée par rapport au descripteur/attribut le plus courant.

Nous allons voir comment faire dans le cas des tables plus tard : aujourd'hui, on va se limiter à de simples tableaux. C'est déjà bien assez compliqué.

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

Les deux fonctions 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 (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 le Shell 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 le Shell, dire si le créateur de la fonction a clairement préciser 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 ce tri. Mais comme 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 un tableau équivalent au premier mais trié.

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(tab2) >>> 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 sur place le tableau sur lequel on fait agir cette méthode.

>>> 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 le Shell (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

ASCII est une table de conversion qu'on peut considérer comme un standard.

Cette table comporte des caractères de 0 à 127 et indique qu'on encode cela sur un octet.

UNICODE est lui une simple association entre un nombre et un caractère.

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.

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 !

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

Si les tableaux s'affichent sans couleur ou si les animations semblent ne pas fonctionner, il faut que vous relanciez la page à jour de façon à mettre vos fichiers CSS à jour.

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

Par exemple avec un tableau trié de 20 éléments et donc d'index compris entre 0 et 19.

06, 08, 09, 13, 18, 37, 37, 59, 60, 60, 61, 68, 70, 80, 80, 83, 83, 89, 91, 96

Sous forme d'un tableau, ce sera plus facile.

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

Cherchons si 40 est présent dans ce tableau.

En recherche séquentielle, on regarderait l'index 0 (06), l'index 1 (08)... Ici, il faut donc 20 boucles et 20 comparaisons.

En recherche dichotomique, nous allons systématiquement supprimer la moitié des données restantes en comparant la valeur associée à l'index central. Si la valeur n'est pas la bonne, on ne gardera que la partie restante à droite ou à gauche.

Etape 1 - Intervalle de départ [ 0 ; 19 ]

  • on considère un point gauche d'index 0 : g = 0.
  • on considère un point droite d'index 19 : d = 19.
  • On calcule l'index central à l'aide d'un division entière : (0+19)//2 donne 9 On aura donc 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

Comme  tableau[9] = 60  et qu'on cherche 40 dans un tableau trié, on ne garde que la partie à gauche du point central d'index 9.

On va alors changer le point droit avec d = 8

On recommence ces opérations sur le nouvel intervalle [0;8].

Etape 2 : Intervalle [0;8]

  • on considère un point gauche d'index 0 : g = 0.
  • on considère un point droite d'index 8 : d = 8.
  • On calcule l'index central à l'aide d'un division entière : (0+8)//2 donne 4 On aura donc c = 4.

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

Comme l'index 4 fait référence à 18 et qu'on cherche 40 dans un tableau trié, on ne garde que la partie à droite de l'index 4.

On va alors changer le point gauche avec g = 5

On recommence ces opérations sur le nouvel intervalle [5;8].

Etape 3 : Intervalle [5;8]

  • on considère un point gauche d'index 0 : g = 5.
  • on considère un point droite d'index 8 : g = 8.
  • On calcule l'index central à l'aide d'un division entière : (5+8)//2 donne 6 On aura donc c = 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

Comme l'index 6 fait référence à 37 et qu'on cherche 40 dans un tableau trié, on ne garde que la partie à droite de l'index 6.

On va alors changer le point gauche avec g = 7

On recommence ces opérations sur l'intervalle [7;8].

Etape 4 : Intervalle [7;8]

  • on considère un point gauche d'index 0 : g = 7.
  • on considère un point droite d'index 8 : g = 8.
  • On calcule l'index central à l'aide d'un division entière : (7+8)//2 donne 6 On aura donc c = 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

Comme l'index 7 fait référence à 59 et qu'on cherche 40 dans un tableau trié, on ne garde que la partie à gauche de l'index 7.

Du coup, on obtient un ensemble vide.

Pas d'étape 4 : l'intervalle restant est vide : l'index droit vaut 6, moins que l'index gauche qui vaut 7 !

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 dichotomique de 50 dans le tableau ci-dessous.

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].

Gauche est placé à 0 et droite est placé à 15.

Questions

  • Que vaut l'index central de l'étape 1 ?
  • Que vaut l'intervalle au début de l'étape 2 ?
  • Que vaut l'index central de l'étape 2 ?
  • Que vaut l'intervalle au début de l'étape 3 ?
  • Que vaut l'index central de l'étape 3 ?

...CORRECTION...

L'index central de l'étape 1 est (0+15)//2 soit 7.

On lit la valeur 68 à cette étape, plus que la valeur 50 recherché.

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

On peut donc supprimer tout ce qui est à droite.

L'intervalle devient donc [0;6] pour le début de l'étape 2.

Le nouvel index central vaut (0+6)//2 soit 3.

On lit la valeur 35 à cet index, moins que la valeur 50 recherchée.

On peut donc supprimer tout ce qui est à gauche.

L'intervalle devient donc [4;6] au début de l'étape 3.

Le nouvel index central est (4+6)//2 soit 5.

On a trouvé 50 qui correspond à la valeur de l'index 5 !

✎ 05° Nous avons fait 3 comparaisons pour effectuer cette recherche. Combien de comparaisons aurait-on dû faire avec une recherche séquentielle ? 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 (16 pouvant s'écrire 24 ):

  • 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 : le pilier et l'autre valeur.
  • Etape finale avec la comparaison sur la dernière valeur possible.

Exemple avec un tableau de 32 valeurs (32 pouvant s'écrire 25 ):

  • 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 finale avec la comparaison sur la dernière valeur possible.

On voit donc que si le nombre n de données est dans l'intervalle ] 2X-1 ; 2X ], on aura besoin au pire de X+1 comparaisons pour trouver ou non si un élément appartient à ce tableau.

On parle d'un coût logarithmique et on peut écrire que cet algorithme est sur 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,

  • On a besoin de 1 000 000 de comparaisons dans le pire des cas avec une recherche séquentielle
  • On a besoin de 20 comparaisons avec une recherche dichotomique !

Ceux qui le désirent pourront voir en fin d'activité pourquoi on peut écrire cela mathématiquement, mais c'est hors programme pour la 1er NSI. Mais c'est intéressant pour ceux qui s'intéressent à l'informatique et ça vous donnera une première approche du logarithme.

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'index 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 index encore disponibles. S'il ne s'agit pas de la bonne valeur, on enlève de l'intervalle de recherche les index 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'implantation): 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.

Pour montrer que l'algorithme se termine, il faut montrer que son déroulement revient à réaliser une condition du type while un > 0un 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.

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 :              .

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

    On peut donc écrire que :

    longueurN+1 = longueurN - (k+1)

    Puisque k ≥ 0 dans le cas d'un nombre impair d'éléments , on réduit bien d'au moins 1 la longueur de l'intervalle.

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

    Cas A : on supprime les k-1 éléments rouges et l'élément central orange, on supprime k-1 + 1, soit k éléments.

    Or, puisque on traite le nombre pair d'éléments, on a k ≥ 1.

    On peut donc écrire que :

    longueurN+1 = longueurN - k

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

    Cas B : on supprime l'élément central orange et les k éléments bleus, on supprime k + 1 éléments.

    Or, puisque on traite le nombre pair d'éléments, on a k ≥ 1.

    On peut donc écrire que :

    longueurN+1 = longueurN - (k+1)

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

07° En reprenant l'essentiel de la démonstration ci-dessus liée au variant longueurN 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 montré dans les deux cas ci-dessus, que le variant longueurN était bien une suite d'entiers strictement décroissante puisqu'on perd au moins toujours un élément.

L'algorithme se termine donc dans tous les cas.

On notera que si on trouve le bon élément, il est possible de quitter l'exécution de l'algorithme avant que l'intervalle soit vide.

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 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.