4.1 Comparaison de la complexité temporelle des recherches linéaire et binaire
Comparons la complexité temporelle des recherches linéaire et binaire.
Recherche linéaire :
- Complexité temporelle :
O(n), oùnest le nombre d'éléments dans le tableau ou la liste. - Meilleur cas :
O(1)— l'élément est trouvé à la première position. - Cas moyen :
O(n/2) = O(n)— l'élément est trouvé en moyenne quelque part au milieu. - Pire cas :
O(n)— l'élément est trouvé à la dernière position ou est absent.
Recherche binaire :
- Complexité temporelle :
O(log n), oùnest le nombre d'éléments dans le tableau ou la liste. - Meilleur cas :
O(1)— l'élément est trouvé au premier essai (élément médian). - Cas moyen :
O(log n)— recherche dans un tableau trié. - Pire cas :
O(log n)— l'élément est trouvé au dernier essai ou est absent.
Exemple d'analyse de la complexité temporelle
Recherche linéaire :
- Tableau
[1, 3, 5, 7, 9, 11, 13], élément recherché 7. - Vérification de chaque élément jusqu'à trouver 7 à l'index 3.
- 4 vérifications ont été nécessaires, ce qui correspond à
O(n).
Recherche binaire :
- Tableau
[1, 3, 5, 7, 9, 11, 13], élément recherché7. - L'élément médian (7) est trouvé au premier essai.
- 1 vérification a été nécessaire, ce qui correspond à
O(log n).
4.2 Avantages et inconvénients de chaque méthode
Examinons les avantages et inconvénients de chaque type de recherche.
Recherche linéaire :
Avantages :
- Simplicité de mise en œuvre : La recherche linéaire est très facile à mettre en œuvre et à comprendre.
- Aucune exigence de tri des données : La recherche linéaire peut s'appliquer à des données non triées.
- Convient aux petits tableaux : La recherche linéaire est efficace pour les tableaux de petite taille.
Inconvénients :
- Efficacité faible pour les grands tableaux : La complexité temporelle
O(n)la rend inefficace pour les grands tableaux. - Temps d'exécution long : Pour les grands tableaux, la recherche linéaire peut prendre beaucoup de temps, surtout si l'élément recherché se trouve vers la fin du tableau ou est absent.
Recherche binaire :
Avantages :
- Efficacité élevée pour les grands tableaux : La complexité temporelle
O(log n)la rend très efficace pour les grands tableaux. - Exécution rapide : La recherche binaire est nettement plus rapide que la recherche linéaire lors du traitement de grands tableaux triés.
Inconvénients :
- Exigence de tri des données : La recherche binaire ne fonctionne qu'avec des tableaux triés, ce qui peut nécessiter un temps supplémentaire pour le tri préalable.
- Complexité de mise en œuvre : La mise en œuvre de la recherche binaire est plus complexe que la recherche linéaire.
4.3 Quand utiliser quelle recherche
Voyons quand utiliser la recherche linéaire et quand utiliser la recherche binaire.
Recherche linéaire.
Utilisez la recherche linéaire lorsque :
- Le tableau ou la liste n'est pas trié.
- La taille du tableau ou de la liste est petite.
- Vous avez besoin de simplicité et d'une solution rapide sans coût supplémentaire pour le tri.
- Vous devez trouver la première occurrence ou toutes les occurrences d'un élément.
- Les données arrivent en temps réel, et leur tri préalable est impossible ou peu pratique.
Recherche binaire.
Utilisez la recherche binaire si :
- Le tableau ou la liste est trié.
- La taille du tableau ou de la liste est grande.
- Vous effectuez souvent des recherches d'éléments dans le même ensemble de données (vous pouvez trier les données une fois au préalable).
- La vitesse de recherche est importante.
- Il est acceptable de passer du temps à trier les données au préalable.
4.4 Exemples de problèmes pour la recherche linéaire
1. Recherche dans une liste non triée
Il faut trouver l'index d'un nombre donné dans une liste non triée de nombres.
Exemple :
def linear_search(arr, target):
for index, element in enumerate(arr):
if element == target:
return index
return -1
arr = [4, 2, 7, 1, 9, 3]
target = 7
print(linear_search(arr, target)) # Sortie : 2
2. Recherche de la première occurrence dans un tableau
Il faut trouver la première occurrence d'un élément donné dans une liste de chaînes.
Exemple :
def linear_search(arr, target):
for index, element in enumerate(arr):
if element == target:
return index
return -1
words = ["apple", "banana", "cherry", "date", "banana"]
target = "banana"
print(linear_search(words, target)) # Sortie : 1
3. Recherche dans des données en temps réel
Trouver un élément dans un flux de données arrivé en temps réel.
Exemple :
import random
def find_in_stream(stream, target):
for index, element in enumerate(stream):
if element == target:
return index
return -1
stream = [random.randint(1, 100) for _ in range(100)]
target = 50
print(find_in_stream(stream, target))
4.5 Exemples de problèmes pour la recherche binaire
1. Recherche dans un tableau trié
Il faut trouver l'index d'un nombre donné dans un tableau trié de nombres.
Exemple :
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(sorted_array, target)) # Sortie : 3
2. Recherche fréquente dans un grand ensemble de données
Rechercher souvent des éléments dans un grand tableau trié de nombres.
Exemple :
import random
sorted_large_array = sorted([random.randint(1, 1000000) for _ in range(1000000)])
target = random.choice(sorted_large_array)
print(binary_search(sorted_large_array, target))
3. Recherche d'un élément dans une base de données triée
Trouver un enregistrement dans une base de données triée par champ clé.
Exemple :
database = sorted([{"id": i, "value": f"record_{i}"} for i in range(100000)])
def binary_search_db(db, target_id):
left, right = 0, len(db) - 1
while left <= right:
mid = (left + right) // 2
if db[mid]["id"] == target_id:
return db[mid]
elif db[mid]["id"] < target_id:
left = mid + 1
else:
right = mid - 1
return None
target_id = 54321
print(binary_search_db(database, target_id))
GO TO FULL VERSION