Recherche par Interpolation

Algorithmique classique

Exercice Débutant · Algo Express · prepa scientifique et economique (CPGE)

Enonce

Rechercher x dans une liste triée d'entiers par recherche par interpolation. Retourner l'indice ou -1.

Signature attendue

def recherche_interpolation(L: list, x: int) -> int:

Exemples

recherche_interpolation([10, 20, 30, 40, 50], 30) → 2
recherche_interpolation([1, 2, 3, 4, 5], 6) → -1
recherche_interpolation([1, 1, 1, 1], 1) → 0

📖 Rappel de cours

Au lieu de couper au milieu, on estime la position de la valeur en supposant les données réparties régulièrement — comme on ouvre un annuaire près de la lettre cherchée.

⚠ Le piège : Sur des données uniformes, le coût tombe à O(log log n) ; sur des données très irrégulières, il remonte à O(n), moins bien que la dichotomie.

← Exercices Python pour la prépa — CPGE scientifique et ECG

Exercices du meme theme

La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.