Algorithme de recherche binaire Python

Recherchez des listes triées en temps logarithmique O (log n). Exécutez et comprenez la recherche binaire en Python, y compris la logique étape par étape, les cas extrêmes et les optimisations.

Essayez dans l'éditeur

Aperçu

La recherche binaire est un algorithme exceptionnellement efficace pour rechercher un élément dans une liste triée. Contrairement à la recherche linéaire qui analyse chaque élément séquentiellement en un temps O(n), la recherche binaire fonctionne en divisant de manière répétée l'intervalle de recherche en deux.

La recherche commence par l'examen de l'élément central du tableau. Si la valeur cible correspond à l'élément du milieu, sa position est renvoyée. Si la cible est plus petite, l’algorithme restreint sa recherche à la moitié inférieure ; si la cible est plus grande, elle la réduit à la moitié supérieure. Ce processus se répète jusqu'à ce que l'élément soit trouvé ou que la taille du sous-tableau tombe à zéro.

Pour implémenter la recherche binaire en Python, nous utilisons deux pointeurs (bas et haut) pour suivre les limites de recherche actives. Étant donné que l'espace de recherche diminue de moitié à chaque étape, l'algorithme s'exécute en un temps O(log n), ce qui le rend idéal pour les bases de données volumineuses.

Sortie de code et d'exécution

Implémentation de recherche binaire itérative standard qui renvoie l'index d'un élément cible dans une liste triée.

binary_search.py

Essayez dans l'éditeur

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = arr[mid]
        
        if guess == target:
            return mid
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1
            
    return -1

# Sorted test dataset
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_val = 23

index = binary_search(data, target_val)
print(f"Dataset: {data}")
print(f"Target: {target_val}")
if index != -1:
    print(f"Target found at index: {index}")
else:
    print("Target not found in dataset")

Sortie terminale

Dataset: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Target: 23
Target found at index: 5

Mise en œuvre étape par étape

Indexation des requêtes et recherche dans les tables de base de données
Recherche de valeurs seuils ou limites dans des plages mathématiques continues
Fonctions de saisie semi-automatique et de recherche dans les champs de texte

Foire aux questions

La liste doit-elle être triée pour que la recherche binaire fonctionne ?

Oui, la recherche binaire repose strictement sur les éléments à trier. Si la liste n'est pas triée, la logique de comparaison s'interrompt et vous devez d'abord trier la liste ou utiliser une recherche linéaire.

Pourquoi utiliser la recherche binaire itérative plutôt que la recherche binaire récursive ?

Bien que la recherche binaire récursive soit élégante, la recherche binaire itérative est souvent préférée en production. L'approche itérative s'exécute dans l'espace auxiliaire O(1), tandis que la recherche récursive prend de l'espace O(log n) en raison de la pile d'appels, risquant un débordement de pile sur des entrées extrêmement volumineuses.

Sujets connexes

Algorithmes de tri Python

Explorez les algorithmes de tri Python. Visualisez le tri par bulles et le tri par fusion de manière native dans un contexte IDE de navigateur.

Tutoriel sur l'algorithme de tri par fusion Python

Découvrez comment implémenter le tri par fusion en Python. Un exemple interactif, étape par étape, de la stratégie de tri Diviser pour régner.

Guide de l'algorithme de tri rapide Python

Explorez l'algorithme de tri rapide en Python. Apprenez la sélection pivot, le partitionnement et la récursivité dans cet exemple de codage interactif.