Exemples de tâches pour la recherche linéaire et binaire

3.1 Tâche de recherche d'un élément dans un tableau à l'aide de la recherche linéaire

Tâche : Un tableau de nombres est donné. Il est nécessaire de trouver l'index d'un numéro donné en utilisant la recherche linéaire. Si le numéro n'est pas trouvé, retourne -1.

Exemple :

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
result = linear_search(arr, target)
print(f"Élément {target} trouvé à l'index {result}")  # Sortie : Élément 7 trouvé à l'index 2

# Exemple d'utilisation pour un élément qui n'est pas dans le tableau :
target = 5
result = linear_search(arr, target)
print(f"Élément {target} trouvé à l'index {result}")  # Sortie : Élément 5 trouvé à l'index -1

Explication :

• La fonction linear_search parcourt chaque élément du tableau arr et le compare à target.
• Si l'élément est trouvé, son index est retourné.
• Si tous les éléments sont vérifiés et que la valeur recherchée n'est pas trouvée, la fonction retourne -1.

Exécution étape par étape :

1. Tableau [4, 2, 7, 1, 9, 3] et valeur recherchée 7.
2. Début de la recherche : le premier élément (4) est comparé à 7 — pas de correspondance.
3. Passage à l'élément suivant (2) — pas de correspondance.
4. Passage à l'élément suivant (7) — correspondance.
5. Retour de l'index 2.

3.2 Tâche de recherche d'un élément dans un tableau trié en utilisant la recherche binaire

Tâche : Un tableau trié de nombres est donné. Il est nécessaire de trouver l'index d'un numéro donné en utilisant la recherche binaire. Si le numéro n'est pas trouvé, retourne -1.

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

# Exemple d'utilisation:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Élément {target} trouvé à l'index {result}")  # Sortie : Élément 7 trouvé à l'index 3

# Exemple d'utilisation pour un élément qui n'est pas dans le tableau :
target = 6
result = binary_search(sorted_array, target)
print(f"Élément {target} trouvé à l'index {result}")  # Sortie : Élément 6 trouvé à l'index -1

Explication :

• La fonction binary_search utilise deux pointeurs (left et right) pour suivre les limites de recherche dans le tableau arr.
• À chaque itération, l'élément médian du tableau est trouvé et comparé à target.
• Si l'élément médian est égal à target, son index est retourné.
• Si target est inférieur à l'élément médian, la recherche continue dans la moitié gauche du tableau.
• Si target est supérieur à l'élément médian, la recherche continue dans la moitié droite du tableau.
• Si les limites se croisent et que l'élément n'est pas trouvé, retourne -1.

Exécution étape par étape :

1. Tableau trié [1, 3, 5, 7, 9, 11, 13] et valeur recherchée 7.
2. Limites initiales de la recherche : left = 0, right = 6.
3. Recherche de l'élément médian : mid = (0 + 6) // 2 = 3.
4. Comparaison de l'élément médian (7) avec target (7) — correspondance.
5. Retour de l'index 3.

3.3 Comparaison et choix de l'algorithme de recherche approprié pour différentes tâches

Comparaison de la recherche linéaire et binaire :

Choix du bon algorithme

Recherche linéaire :

• Utilisée lorsque les données ne sont pas triées.
• Adaptée pour les petits tableaux ou listes.
• Appliquée lorsque le nombre d'éléments est faible et que le temps d'exécution n'est pas critique.

Recherche binaire :

• Appliquée lorsque les données sont triées.
• Idéale pour les grands tableaux où la vitesse de recherche est importante.
• Efficace si une recherche fréquente est requise dans le même jeu de données (les données peuvent être triées à l'avance).

3.4 Exercices pratiques pour consolider le matériel

Exercice 1 : Recherche linéaire

Un tableau de nombres est donné. Écrivez une fonction pour rechercher un numéro donné en utilisant la recherche linéaire. La fonction doit retourner l'index de l'élément trouvé ou -1 si l'élément n'est pas trouvé.

Exemple :

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
result = linear_search(arr, target)
print(f"Élément {target} trouvé à l'index {result}")  # Sortie : Élément 7 trouvé à l'index 2

# Tests supplémentaires :
assert linear_search(arr, 9) == 4
assert linear_search(arr, 5) == -1

Exercice 2 : Recherche binaire

Un tableau trié de nombres est donné. Écrivez une fonction pour rechercher un numéro donné en utilisant la recherche binaire. La fonction doit retourner l'index de l'élément trouvé ou -1 si l'élément n'est pas trouvé.

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

# Exemple d'utilisation:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Élément {target} trouvé à l'index {result}")  # Sortie : Élément 7 trouvé à l'index 3

# Tests supplémentaires :
assert binary_search(sorted_array, 1) == 0
assert binary_search(sorted_array, 13) == 6
assert binary_search(sorted_array, 6) == -1

Exercice 3 : Comparaison de la recherche linéaire et binaire

Un tableau de nombres est donné. Écrivez deux fonctions pour rechercher un numéro donné : une utilisant la recherche linéaire, l'autre la recherche binaire. Comparez les performances des deux fonctions sur de grands tableaux.

Exemple :

import time
import random

# Recherche linéaire
def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# Recherche binaire
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

# Génération d'un grand tableau
large_array = [random.randint(0, 1000000) for _ in range(1000000)]
sorted_large_array = sorted(large_array)
target = random.choice(large_array)

# Comparaison des performances
start_time = time.time()
linear_search(large_array, target)
print(f"Recherche linéaire a pris : {time.time() - start_time:.6f} secondes")

start_time = time.time()
binary_search(sorted_large_array, target)
print(f"Recherche binaire a pris : {time.time() - start_time:.6f} secondes")