Dichotomie sur un tableau non trie

Le piege

Appliquer la recherche dichotomique sur un tableau non trie en esperant un resultat correct. L'algorithme peut s'executer sans erreur Python, mais renvoie souvent une fausse reponse.

Pourquoi c'est faux

L'invariant repose sur : « si la cible existe, elle est dans l'intervalle [gauche, droite] ». Sans ordre, eliminer une moitie peut eliminer la valeur cherchee.

Exemple

Tableau : [8, 3, 9, 1]  (non trie), cible 8 (pourtant presente, a l'indice 0)
indice 1 (milieu) : 3 < 8  → on ne garde que la droite  [9, 1]
indice 2 (milieu) : 9 > 8  → on ne garde que la gauche  : plus rien
→ la dichotomie renvoie -1 : elle conclut a tort que 8 est absent.

Bonne pratique

Trier d'abord (cout O(n log n)) puis dichotomie, ou utiliser la recherche sequentielle si le tableau n'est pas trie et n est petit.