9.1 Exemples de problèmes résolus avec la recherche linéaire et binaire
Recherche linéaire
Problème de recherche d'un élément dans un tableau : Un tableau de nombres et une valeur cible sont donnés. Il est nécessaire de trouver l'index de la valeur cible dans le tableau.
Solution : Utilisez la recherche linéaire pour vérifier chaque élément du tableau.
Exemple d'implémentation :
def linear_search(arr, target):
for index, element in enumerate(arr):
if element == target:
return index
return -1
# Exemple d'utilisation :
arr = [4, 2, 7, 1, 9, 3]
target = 7
print(linear_search(arr, target)) # Sortie : 2
Recherche binaire
Problème de recherche d'un élément dans un tableau trié : Un tableau trié de nombres et une valeur cible sont donnés. Il est nécessaire de trouver l'index de la valeur cible dans le tableau.
Solution : Utilisez la recherche binaire pour diviser le tableau en moitiés et rechercher la valeur cible.
Exemple d'implémentation :
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
# Exemple d'utilisation :
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(sorted_array, target)) # Sortie : 3
9.2 Problèmes d'utilisation de hash tables pour optimiser la recherche
1. Recherche de doublons dans un tableau
Problème : Un tableau de nombres est donné. Il est nécessaire de trouver et de retourner tous les doublons dans le tableau.
Solution : Utilisez une hash table pour suivre les nombres déjà rencontrés. Si un nombre apparaît à nouveau, ajoutez-le à la liste des doublons.
Exemple d'implémentation :
def find_duplicates(arr):
seen = set()
duplicates = []
for item in arr:
if item in seen:
duplicates.append(item)
else:
seen.add(item)
return duplicates
# Exemple d'utilisation
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr)) # Sortie : [2, 4]
2. Trouver des paires avec une somme donnée
Problème : Un tableau de nombres et une valeur cible de somme sont donnés. Il est nécessaire de trouver toutes les paires de nombres qui donnent la somme cible.
Solution : Utilisez une hash table pour stocker les nombres et vérifier s'ils forment une paire avec le nombre actuel qui donne la somme cible.
Exemple d'implémentation :
def find_pairs_with_sum(arr, target_sum):
seen = set()
pairs = []
for num in arr:
complement = target_sum - num
if complement in seen:
pairs.append((complement, num))
seen.add(num)
return pairs
# Exemple d'utilisation
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum)) # Sortie : [(1, 5), (7, -1), (1, 5)]
9.3 Utilisation combinée de différentes méthodes de recherche
Dans les problèmes complexes, il est souvent nécessaire d'utiliser plusieurs méthodes de recherche pour atteindre la meilleure efficacité. L'utilisation combinée de la recherche linéaire, de la recherche binaire et des hash tables permet de résoudre les problèmes de manière plus efficace et flexible.
Exemple 1 : Trouver un élément dans un tableau et vérifier son existence dans un autre tableau
Deux tableaux de nombres sont donnés. Il est nécessaire de trouver les éléments du premier tableau qui existent dans le deuxième tableau.
Solution :
- Utilisez une hash table pour stocker les éléments du deuxième tableau.
- Pour chaque élément du premier tableau, vérifiez son existence dans la hash table.
Exemple d'implémentation :
def find_common_elements(arr1, arr2):
hash_table = set(arr2) # Hash table pour le deuxième tableau
common_elements = []
for element in arr1:
if element in hash_table:
common_elements.append(element)
return common_elements
# Exemple d'utilisation :
arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6, 7]
print(find_common_elements(arr1, arr2)) # Sortie : [3, 4, 5]
Exemple 2 : Vérifier si un sous-tableau est un tableau d'anagrammes en utilisant une hash table
Un tableau de chaînes de caractères et une chaîne modèle sont donnés. Il est nécessaire de vérifier si une sous-chaîne quelconque du tableau de chaînes est une anagramme du modèle.
Solution :
- Utilisez une hash table pour compter la fréquence des caractères dans le modèle.
- Parcourez le tableau de chaînes en utilisant une « fenêtre glissante » pour vérifier chaque sous-chaîne par rapport aux fréquences des caractères.
Exemple d'implémentation :
from collections import Counter
def is_anagram(s1, s2):
return Counter(s1) == Counter(s2)
def find_anagram_substring(arr, pattern):
pattern_length = len(pattern)
pattern_count = Counter(pattern)
for i in range(len(arr) - pattern_length + 1):
substring = arr[i:i + pattern_length]
if is_anagram(substring, pattern):
return True
return False
# Exemple d'utilisation :
arr = "cbabadcbbabbcbabaabccbabc"
pattern = "abbc"
print(find_anagram_substring(arr, pattern)) # Sortie : True
9.4 Exercices pratiques pour consolider le matériel
Exercice 1 : Recherche d'un élément dans un tableau non trié
Un tableau de nombres et une valeur cible sont donnés. Il est nécessaire de trouver l'index de la valeur cible dans le tableau. Utilisez la recherche linéaire.
Exemple :
def linear_search(arr, target):
for index, element in enumerate(arr):
if element == target:
return index
return -1
# Exemple d'utilisation :
arr = [10, 20, 30, 40, 50]
target = 30
print(linear_search(arr, target)) # Sortie : 2
Exercice 2 : Recherche de doublons dans un tableau
Un tableau de nombres est donné. Trouvez et retournez tous les doublons dans le tableau en utilisant une hash table.
Exemple :
def find_duplicates(arr):
seen = set()
duplicates = []
for item in arr:
if item in seen:
duplicates.append(item)
else:
seen.add(item)
return duplicates
# Exemple d'utilisation :
arr = [1, 3, 5, 3, 7, 9, 1]
print(find_duplicates(arr)) # Sortie : [3, 1]
GO TO FULL VERSION