Initiation aux algorithmes

Algorithme et langage de programmation

Le rôle de l'algororithmique est de proposer pour un problème donné, une solution qui peut, après traduction, être exécutée ou réalisée sur un ordinateur.

D'un problème, on détermine les intervenants et leurs relations à travers une analyse afin d'énoncer une solution (l'algorithme) qui, traduit, donnera le programme exécutable sur un ordinateur.

• définir des instructions pour résoudre un problème
• algo = écrire une recette / programmation = faire la recette
• abstraction de langue
• organigramme vs pseudo-code

La schématisation des algorithmes par des organigrammes est peu utilisée car elle amène deux problèmes :

• une lourdeur quand il y a beaucoup d'instructions
• l'apprentissage d'une programmation dite non structurée

Familles d'instructions

• affectation
• lecture/écriture
• test
• boucle

Ordinateur ("Je est un autre")

Entrées / sorties

Un ordinateur dispose de ports d'entrées et de ports de sorties qui lui permettent respectivement, d'acquérir des données, des informations et de transmettre d'autres données ou informations.
Les données provenant d'un scanner seront des entrées alors que les données transmises à une imprimante, seront des sorties.

Lire et écrire 1/2

De la même manière, un programme est une série d'instructions destinées à un ordinateur. Les instructions de lecture/écriture doivent se comprendre comme des actions réalisées par le programme (et non le développeur).
Dès lors :

• l'instruction lire correspond à l'acquisition de données (entrée)
• l'instruction écrire correspond à l'affichage d'une information (sortie)

Variables

Les variables permettent de stocker une information susceptible d'évoluer durant l'exécution du programme.

Le nom de la variable respecte les règles suivantes :

1. doit commencer par une lettre ou le caractère underscore ( _ )
2. ne peut pas commencer par un chiffre
3. doit contenir une ou plusieurs lettres, un ou plusieurs chiffres et/ou un ou plusieurs underscores
4. ne doit contenir aucun espace
5. est sensible à la casse (minuscule / majuscule)
6. évite l'usage de caractères accentués

Le nom d'une variable doit être défini de manière à aider à la compréhension des instructions / du programme : compteur, ville.

Déclaration de variables

Types de variables

• numériques :
  • entier
  • réel
• alphanumériques :
  • caractère
  • chaîne de caractères
• booléens (vrai / faux)

Les caractères et chaînes de caractères doivent être placés entre quotes.

Pour les dates, on crée 3 variables de type entier pour le jour, le mois et l'année.

Déclaration

Celle-ci est faite au début de l'algorithme, avant toutes autres instructions.

Variable taille_panier : entier
Variables montant, tva, montant_tva, montant_total : réel
Variables nom_client : chaîne de caractères

Variables
    taille_panier : entier
    montant, tva, montant_tva, montant_total : réel
    nom_client : chaîne de caractères

Déclarer n'est pas initialiser !

Une variable déclarée est vide de tout contenu tant qu'elle n'a pas été initialisée. Tant que l'initialisation n'a pas été faite vouloir connaître son contenu entraine une erreur (lecture, comparaison, etc.).

Type et contenu

Une fois déclarée, une variable ne peut contenir que le type qui lui a été attribué.

Une variable déclarée avec un type ne peut contenir que des valeurs de ce même type.

Vouloir stocker une valeur de type chaîne de caractères dans une variable déclarée en type entier est une erreur d'écriture.

Affectation

L'affectation est l'instruction de base concernant une variable : on attribue un contenu/une valeur à notre variable. L'affectation se fait en utilisant l'opérateur de la manière suivante :

ma_variable  ma_valeur

Une instruction de type affectation stocke dans la variable placée à gauche de l'opérateur le résultat situé à droite de l'opérateur.

prix_panier  12.95

L'intérêt de créer une variable est de lui faire stocker une information que l'on souhaite conserver dans le but de l'utiliser plus tard dans le cours du programme (un calcul, un affichage, etc.)
Par exemple, le nom d'un acheteur connecté sur un site e-commerce est stocké ainsi pour servir à divers endroits du site ("Bienvenue Untel", "Si vous n'êtes pas Untel, merci de vous déconnecter", etc.)

Variables A, B : entier
Début
    A  1
    B  A + 3
    A  3
Fin

Variables A, B, C : entier
Début
    A  5
    B  3
    C  A + B
    A  2
    C  B – A
Fin

Variables A, B, C : entier
Début
    A  3
    B  10
    C  A + B
    B  A + B
    A  C
Fin

Variables A, B : entier
Début
    A  5
    B  2
    A  B
    B  A
Fin

Structure d'un algorithme

• nom du programme, de la fonction ou de la procédure
• déclaration de variables
• mot clé "début" indiquant le début des instructions du programme, de la fonction ou de la procédure
• instructions
• mot clé "fin" indiquant la fin des instructions du programme, de la fonction ou de la procédure

Programme Calcul_montant_tva
Variable montant, tva, montant_tva, total : réel
Début
    montant  100
    tva  20
    total  montant * (1 + tva/100)
    montant_tva  total - montant
Fin

Lire et écrire 2/2

Une autre méthode pour réaliser une affectation consiste à demander une valeur (à un utilisateur par exemple).
Pour cela, il faut utiliser les mots clefs lire et écrire. L'instruction "écrire" indique au programme quand envoyer une information vers une interface de sortie (généralement, un écran), et "lire", quand récupérer une information via une interface d'entrée (généralement via un clavier).

Au moment où le programme exécute une instruction "lire", il s'arrête en attendant que lui soit fourni ce qu'il attend.

Variable age : entier
Début
    écrire "Merci d'indiquer votre âge"
    lire age
    écrire "Vous avez "
    écrire age
    écrire " ans"
Fin

Opérateurs

Parmi les opérateurs, il y a les opérateurs arithmétiques classiques :

• addition : +
• soustraction : -
• multiplication : *
• division : /

Il y a également :

• l'opérateur de puissance : ^
• l'opérateur de concaténation : &
• les opérateurs logiques : ET, OU et NON

écrire "La ville est : " & ville

Variables A, B, C : chaîne de caractères
Début
A  "423"
B  "12"
C  A + B
Fin

Variables A, B, C : chaîne de caractères
Début
A  "423"
B  "12"
C  A & B
Fin

Opérateur de comparaison

La condition nécessite l'utilisation d'opérateurs de comparaison :

• égal à : =
• différent de : != ou <>
• strictement plus petit que : <
• strictement plus grand que : >
• plus petit ou égal à : <=
• plus grand ou égal à : >=

Ordre alphabétique

Pour ordonner des caractères ou chaînes de caractères, ce qui est communément admis sont les règles suivantes (basées sur les tables ASCII):

• A est inférieur à B
• a est inférieur à b
• A est inférieur à a
• Z est inférieur à a

Donc l'ordre est le suivant : A..Za..z.

Structures alternatives ou tests

Il est possible, en fonction d'un élément (le contenu d'une variable, le résultat d'une opération, etc.) de faire en sorte que notre programme réalise des instructions différentes. Pour cela, on utilise la structure suivante :

si booléen alors
    instructions
finsi

ou la suivante :

si booléen alors
    instructions
sinon
    instructions
finsi

Pour distinguer ce qui est mot clé de ce qui ne l'est pas, soit on inscrit en majuscule le mot clé, soit on le souligne.

A la place du "booléen", il y aura soit une expression dont la valeur est VRAI ou FAUX :

• soit une variable de type booléen
• soit une condition

Variable temp : entier
Début
	écrire "Entrez la température de l’eau :"
	lire temp
	Si temp <= 0 Alors
  		écrire "C’est de la glace"
	FinSi
	Si temp > 0 Et temp < 100 Alors
  		écrire "C’est du liquide"
	Finsi
	Si temp > 100 Alors
  		écrire "C’est de la vapeur"
	Finsi
Fin

Une simplification avec l'utilisation de Sinon :

Variable temp : entier
Début
    écrire "Entrez la température de l’eau :"
    lire temp
    Si temp <= 0 Alors
        écrire "C’est de la glace"
    Sinon
        Si temp < 100 Alors
            écrire "C’est du liquide"
        Sinon
            écrire "C’est de la vapeur"
        Finsi
    Finsi
Fin

Une autre simplification en utilisant SinonSi

Variable temp : entier
Début
    écrire "Entrez la température de l’eau :"
    lire temp
    Si temp <= 0 Alors
        écrire "C’est de la glace"
    SinonSi temp < 100 Alors
        écrire "C’est du liquide"
    Sinon
        écrire "C’est de la vapeur"
    Finsi
Fin

Enfin en utilisant des variables booléenes :

Variable temp : entier
Variables est_glace, est_vapeur : booléen
Début
    écrire "Entrez la température de l’eau :"
    lire temp
    est_glace  temp <= 0
    est_vapeur  temp < 100
    Si est_glace Alors
        écrire "C’est de la glace"
    SinonSi est_vapeur Alors
        écrire "C’est du liquide"
    Sinon
        écrire "C’est de la vapeur"
    Finsi
Fin

Variables jour, mois, annee : entier
...
Début
jour  aujourdhui('jour')
mois  aujourdhui('mois')
annee  aujourdhui('annee')
...
...
Fin
                    

Opérateurs booléens ou opérateurs logiques

Les opérateurs logiques servent dans les tests de logique. Les tests de logique permettent d'orienter l'exécution d'un programme vers une série d'instruction ou une autre : si l'utilisateur connecté est une femme, il faut lui proposer les promotions sur des vêtements féminins, si c'est un homme, les promotions sur ceux masculins.
Dans certains cas, plusieurs critères (~ tests logiques) sont nécéssaires pour décider d'une action (~ série d'instructions) à réaliser :

• S'il fait plus de 17°C ET qu'il y a le soleil, je vais en ville à pied;
• si Pierre me prête sa voiture OU que je peux en louer une, je vais au ski cet hiver.

Le ET et le OU inscrits ci-dessus sont des opérateurs de logique ; les tests de logique de part et d'autre de ces opérateurs vont avoir un résultat (vrai ou faux) et, en fonction de l'opérateur, la valeur de l'ensemble des tests va être déterminé (là aussi, soit vrai, soit faux).

Il existe 4 opérateurs servant aux opérations de tests :

• ET
• OU (dans le sens : l'un ou l'autre, peu importe)
• XOR à considérer comme "ou bien" (dans le sens : l'un ou l'autre, pas les deux en même temps)
• NON (dans le sens "n'est pas")

Attention lors de la création d'une variable booléenne, il ne faut pas mettre les quotes au niveau de la valeur

Variable frais_port_offert : booléen
Début
frais_port_offert  "vrai"  ---- ERREUR de type
frais_port_offert  vrai
Fin

Avec ces opérateurs, il existe des règles ou tables dites de Boole, du nom du mathématicien les ayant déterminées.

Table du ET

Il faut que les 2 opérandes soient vrais pour que l'ensemble retourne vrai.

S'il fait plus de 17°C et qu'il y a le soleil, je vais en ville à pied.

1. il fait 21°C et le soleil est présent, alors ?
2. il fait 15°C et le soleil est présent, alors ?
3. il fait 21°C et il pleut, alors ?
4. il fait 7°C et il pleut, alors ?

Table du OU

Il faut que l'un des 2 opérandes soit vrai pour que l'ensemble retourne vrai.

Si Pierre me prête sa voiture OU que je peux en louer une, je vais au ski cet hiver.

1. Pierre me prête sa voiture et je peux en louer une, alors ?
2. Pierre ne me prête pas sa voiture et je peux en louer une, alors ?
3. Pierre me prête sa voiture et je ne peux pas en louer une, alors ?
4. Pierre ne me prête pas sa voiture et je ne peux pas en louer une, alors ?

Table du XOR

Il faut que les opérandes soient de valeur opposée pour que l'ensemble retourne vrai.

Table du NON

Renvoie la valeur opposée de l'opérande.

Des simplifications de test sont possibles en utilsant les opérateurs booléens.

Si il fait trop chaud Alors
    Ouvrir la fenêtre
Sinon
    Fermer la fenêtre
Finsi

Si il ne pleut pas Alors
    Ouvrir la fenêtre
Sinon
    Fermer la fenêtre
Finsi

ET et OU sont interchangeables

Selon la transformation de De Morgan :

• NON(A ET B) = NON(A) OU NON(B)
• NON(A OU B) = NON(A) ET NON(B)

De ses règles, la transformation suivante :

Si A ET B Alors
    Instructions 1
Sinon
    Instructions 2
Finsi

équivaut à :

Si NON(A) OU NON(B) Alors
    Instructions 2
Sinon
    Instructions 1
Finsi

Remarquez l'inversion des instructions

Si il fait trop chaud ET il ne pleut pas Alors
    Ouvrir la fenêtre
Sinon
    Fermer la fenêtre
Finsi

Conditions composées

Vérifier si un montant est compris entre 0 et 50 euros, revient à tester deux conditions :

• montant est supérieur (ou égal) à 0
• montant est inférieur (ou égal) à 50

Il n'est pas possible de vérifier si x est compris entre 10 et 100 en une seule condition.

Pour lier les deux conditions, il faut utiliser un opérateur logique.

Boucle

• instruction(s) répétée(s) un certain nombre de fois
• instruction(s) itérative(s)
• nombre connu de répétition ou non

Tant que

TantQue booléen Faire
  …
  Instructions
  …
FinTantQue

Un exemple d'utilisation :

Variable rep : caractère
Début
    rep  ""
    écrire "Comptez vous partir en vacances ? (O/N)"
    TantQue rep != "O" et rep != "N" Faire
        lire rep
    FinTantQue
Fin

Pour

Une boucle tant que ayant un compteur qui est incrémenté à chaque passage de boucle

Variable compteur : entier
Début
    compteur  0
    TantQue truc < 15 Faire
        compteur  compteur + 1
        écrire "Passage numéro : " & compteur
    FinTantQue
Fin

devient :

Variable compteur : entier
Début
    Pour compteur de 1 à 15
        écrire "Passage numéro : " & compteur
    FinPour
Fin

ou, en indiquant le pas de l'incrémentation :

Variable compteur : entier
Début
    Pour compteur de 1 à 15 par 1
        écrire "Passage numéro : " & compteur
    FinPour
Fin

La structure de la boucle Pour est donc la suivante :

Pour compteur de Initial à Final Par ValeurDuPas
…
Instructions
…
FinPour

Les boucles imbriquées sont possibles mais il faut tenir compte de leur complexité d'exécution

Variables compteur_1, compteur_2 : entier
Début
    Pour compteur_1 De 1 à 10
        écrire "Il est passé par ici"

        Pour compteur_2 De 1 à 6
            écrire "Il repassera par là"
        FinPour
    FinPour
Fin

Tableau

Tableau à longueur connue

Les tableaux sont des conteneurs et comme toutes les variables, ils peuvent contenir divers types de valeur mais à leur déclaration, le type qui leur est associé doit être indiqué :

Tableau nom_tab(taille_tab) : type_valeur_contenue

Exemple :

Tableau note(10) : entier
Variable compteur : entier

Dans le cas ci-dessus, un tableau de 10 éléments de type entier est déclaré : il ne pourra contenir que des entiers et sa longueur est fixée à 10 éléments, pas plus. La position dans un tableau est appelée "indice".

Le premier indice d'un tableau est 0

L'indice d'un tableau va de 0 à n-1, avec n indiquant la taille du tableau.

Tableau note(10) : entier

L'indice maximum de ce tableau sera 9.

La lecture et l'écriture dans un tableau nécessite d'indiquer une position dans le tableau en placant celle-ci entre crochet :

note[0]  15
écrire "Vous avez eu la note de " & note[0]

Toute cellule d'un tableau doit être initialisée avant d'être utilisable

L'accès à un indice d'un tableau qui n'a pas été initialisée entrainera une erreur.
C'est pourquoi il est recommandé d'initialiser chaque emplacement d'un tableau avec une valeur par défaut.

Pareillement, l'accès à un indice qui n'existe pas entrainera une erreur :

Tableau note(10) : entier
note[10]  12

Tableau à longueur inconnue

Certaines fois, la taille du tableau n'est pas connue à l'avance ou il vaut mieux laisser l'utilisateur définir la taille. Dans ces cas là, il faut utiliser le mot clé "redim" pour définir la taille du tableau :

Tableau participant() : chaîne de caractères
Début
    écrire "Combien de participants ?"
    lire nb
    redim participant(nb)
Fin

La modification d'un tableau existant peut entraîner des erreurs et doit donc être utilisée avec sagesse.

Pour connaître la taille d'un tableau, il faut utiliser la fonction taille qui retourne la taille du tableau transmis en argument.

Tableau test(10) : entier
Variable compte : entier
Début
    compte  taille(test)
Fin

Exercices sur la manipulation des tableaux

"Flag" ou gestion asymétrique de variable booléenne

La recherche d'un élément d'un tableau peut se faire en utilisant un flag ou drapeau, indiquant que l'élément a été trouvé ou non. Il s'agit d'une valeur de type booléenne initialisée à faux et si lors du parcours du tableau, la valeur est trouvée, la valeur vrai est affectée à la variable.

Déterminer le but

Le but d'un algorithme est de résoudre un problème ou de répondre à une question.
Comment déterminer le plus petit multiple entre deux chiffres ? Quelle est la valeur la plus grande d'un tableau ?

L'auteur n'est pas toujours soi-même et il faut parfois "décoder" ce qu'un autre à fait.
Pour y parvenir, la solution la plus simple est d'imaginer un jeu d'entrées simples (des variables, des tableaux... ce que le programme manipule) et de déterminer comment ce jeu est modifié.

tableau t(10) : entier
variable v, i, j : entier

Debut
	pour i de 0 à 9 par 1
		lire t[i]
	finpour

	lire v

	j <- 0
	pour i de 0 à 9 par 1
		si t[i] = v alors
			j <- j + 1
		finsi
	finpour
	ecrire j
Fin

tableau t(10) : entier
variable v, i : entier
variable j : booléen

Debut
	pour i de 0 à 9 par 1
		lire t[i]
	finpour

	lire v

	j <- faux
	i <- 0
	tantque j = faux ET i <= 9 faire
		si t[i] = v alors
			j <- vrai
		finsi
		i <- i + 1
	fintantque

	si j = vrai alors
		ecrire 1
	sinon
		ecrire 0
	finsi
Fin

tableau t(10) : entier
variable v, i, c : entier

Debut
	pour i de 0 à 9 par 1
		v <- 0
		tantque v <= 0 OU v > 100 faire
			lire v
		fintantque
		t[i] <- v
	finpour

	c <- 0
	pour i de 0 à 9 par 1
		si t[i] < 50 alors
			c <- c + 1
		finsi
	finpour

	ecrire c
Fin

tableau t(10) : entier
variable k, v, i, c : entier
variable m : réel

Debut
	lire k
	redim t(k)

	pour i de 0 à k-1 par 1
		v <- 0
		tantque v < 0 OU v >= 60 faire
			lire v
		fintantque
		t[i] <- v
	finpour

	c <- 0
	pour i de 0 à k-1 par 1
		c <- c + t[i]
	finpour

	m <- c / 3 / k

	ecrire m
Fin

Tri d'un tableau

Tri par sélection/extraction

L'algorithme parcourt le tableau à la recherche de l'élément le plus petit.
1 - 2 - 7 - 10 - 8 - 5 - 6 - 3 - 4 - 9
1 - 2 - 7 - 10 - 8 - 5 - 6 - 3 - 4 - 9
1 - 2 - 3 - 10 - 8 - 5 - 6 - 7 - 4 - 9
1 - 2 - 3 - 4 - 8 - 5 - 6 - 7 - 10 - 9
1 - 2 - 3 - 4 - 5 - 8 - 6 - 7 - 10 - 9
1 - 2 - 3 - 4 - 5 - 6 - 8 - 7 - 10 - 9
1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 10 - 9
1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 10 - 9
1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10
1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10

Pour réaliser cela, 2 boucles imbriquées sont nécessaires, la première permettant de sélectionner l'élément à comparer et la seconde permettant de comparer l'élément avec les autres.

Tri à bulle

L'algorithme parcourt le tableau t en intervertissant les indices i et i+1 si t[i] est plus grand que t[i+1]. En avançant ainsi, le plus grand élément trouvé est repoussé à droite.
2 - 4 - 7 - 8 - 5 - 6 - 3 - 1 - 9 - 10
2 - 4 - 7 - 5 - 6 - 3 - 1 - 8 - 9 - 10
2 - 4 - 5 - 6 - 3 - 1 - 7 - 8 - 9 - 10
2 - 4 - 5 - 3 - 1 - 6 - 7 - 8 - 9 - 10
2 - 4 - 3 - 1 - 5 - 6 - 7 - 8 - 9 - 10
2 - 3 - 1 - 4 - 5 - 6 - 7 - 8 - 9 - 10
2 - 1 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10
1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10
1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10

Il existe une variante de ce tri appelée tri à bulle amélioré qui va procéder de la même manière avec la différence que, étant donné que le plus grand élément trouvé est placé en bout, on réduit la taille d'un cycle à chaque passage : on réduit ainsi le nombre de comparaisons réalisées.
2 - 4 - 7 - 8 - 5 - 6 - 3 - 1 - 9 - 10
2 - 4 - 7 - 5 - 6 - 3 - 1 - 8 - 9 - 10
2 - 4 - 5 - 6 - 3 - 1 - 7 - 8 - 9 - 10
2 - 4 - 5 - 3 - 1 - 6 - 7 - 8 - 9 - 10
2 - 4 - 3 - 1 - 5 - 6 - 7 - 8 - 9 - 10
2 - 3 - 1 - 4 - 5 - 6 - 7 - 8 - 9 - 10
2 - 1 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10
1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10
1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10
(en gras les éléments comparés lors du cycle)

Tri fusion (pour information)

L'algorithme réalise deux opérations qui sont la découpe d'un tableau en deux et la fusion de tableaux ordonnés.
** 4 - 2 - 7 - 8 - 5 - 6 - 3 - 1
-> 4 - 2 - 7 - 8 | 5 - 6 - 3 - 1
-> 4 - 2 | 7 - 8 | 5 - 6 | 3 - 1
-> 2 - 4 | 7 - 8 | 5 - 6 | 1 - 3
-> 2 - 4 - 7 - 7 | 1 - 3 - 5 - 6
-> 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8

1. si la taille du tableau est supérieure à 2 :
   1. le tableau est coupé en 2 tableaux
   2. chaque nouveau tableau obtenu est testé sur sa taille et réalise le point 1 ou 2
2. si la taille du tableau est inférieure ou égale à 2:
   1. les éléments du tableau sont triés
   2. le tableau est fusionné avec le tableau dont il a été séparé précédemment

Tri rapide (pour information)

L'algorithme choisit aléatoirement une position dans le tableau et la valeur trouvée (appelée pivot) sert à organiser les autres valeurs par rapport au pivot en ayant d'un coté les valeurs inférieures au pivot et d'un autre, les valeurs supérieures. Une fois fait, un pivot est choisi pour chacune des sous listes et le processus précédent est à nouveau réalisé.
** 4 - 2 - 7 - 8 - 5 - 6 - 3 - 1
-> 4 - 2 - 7 - 8 - 5 - [6] - 3 - 1
-> 4 - 2 - 5 - 3 - 1 - [6] - 7 - 8
** 4 - 2 - 5 - [3] - 1 - 6 - [7] - 8
-> 2 - 1 - [3] - 4 - 5 - 6 - [7] - 8
...

Recherche dans un tableau

Recherche basique

L'algorithme parcourt le tableau en comparant chaque valeur de case avec l'élément recherché. Il s'agit là de la méthode la plus simple mais la moins efficace, car plus il y a de données et plus la recherche sera longue.

Recherche séquentielle dans un tableau trié

L'algorithme parcourt le tableau en comparant chaque valeur de case avec l'élément recherché. Mais cette fois-ci, si l'élément recherché est plus grand (recherche croissante) que l'élément comparé, la recherche peut s'arrêter : l'élément recherché est absent.

Exemple : on recherche la lettre D dans la série de lettre ABEFG. Dès qu'on atteint E, on peut s'arrêter, la lettre n'est pas dans la série.

Recherche par dichotomie (ou recherche dichotomique)

Cet algorithme de recherche nécessite également un tableau trié.
Le principe appliqué est celui qu'on utilise lorsqu'on recherche un mot dans un dictionnaire. L'algorithme compare la valeur recherchée avec la valeur trouvée au centre du tableau : si la valeur recherché est inférieure, la recherche va se poursuivre à l'intérieur de la première moitié du tableau ; sinon dans la seconde moitié. Quel que soit la moitié choisie, l'algorithme, va à nouveau couper en deux le jeu des possibilités. Etc.