Qu'est-ce que la recherche binaire?

Une recherche binaire est un algorithme de recherche utilisé pour rechercher des éléments cibles dans un conteneur où les éléments doivent être organisés par ordre croissant. Généralement, la recherche binaire est utilisée pour rechercher le numéro d'index de l'élément cible dans un tableau trié.

La recherche binaire utilise l'approche Divide and Conquers, dans laquelle il divise le tableau en parties égales jusqu'à ce qu'il trouve l'élément cible.

Un algorithme de recherche binaire est implémenté itératif ainsi qu'une déclaration récursive. La recherche binaire est plus efficace et plus rapide par rapport à la recherche linéaire.

Algorithme de recherche binaire

1. Trier et organiser les éléments du tableau art Dans l'ordre croissant.
2. Les algorithmes comparent l'élément central n avec l'élément cible cible.
3. L'algorithme renvoie l'indice de position de l'élément central si l'élément cible se révèle égal à l'élément central,
4. L'algorithme recherche la moitié inférieure du tableau si l'élément cible est inférieur à l'élément central.
5. L'algorithme recherche la moitié supérieure du tableau si l'élément cible est supérieur à l'élément central.
6. L'algorithme continue de répéter les 4e et 5e étapes jusqu'à ce que la longueur du tableau devienne une ou moins de 1.

À la fin, soit la valeur d'index de l'élément est renvoyée, soit l'élément n'existe pas dans le tableau.

Pseudocode de recherche binaire

Itératif

fonction binary_search (arr, n, cible) est
Gauche: = 0
à droite: = n - 1
tandis que la gauche ≤ à droite fait
Middle: = Floor ((gauche + à droite) / 2)
Si Arr [Middle] Target alors
à droite: = milieu - 1
autre:
Retour au milieu
retourne sans succès

Récursif

fonction binary_search (arr, gauche, droite, cible) est
Si droite> = gauche
Middle = (gauche + droite) // 2
Si arr [middle] == cible
Retour au milieu
sinon si arr [middle]> tarrget
return binary_search (arr, bas, mi-1, cible)
autre
return binary_search (arr, mid + 1, à droite, cible)
autre
retourne sans succès

Implémentez la recherche binaire dans Python

Itératif
Dans l'approche itérative, nous utilisons les boucles pour implémenter la recherche binaire.

def binary_search (arr, n, cible):
gauche = 0
à droite = n-1
Middle = 0
À gauche<=right:
Middle = (droit + gauche) // 2
# Si l'élément central est égal à l'élément cible
Si arr [middle] == cible:
Retour au milieu
# Si l'élément cible est supérieur à l'élément central
Elif arr [Middle]< target:
gauche = milieu + 1
# Si l'élément cible est inférieur à l'élément central
autre:
Droite = Middle-1
# Si l'élément cible n'est pas présent dans le tableau
retour -1
Si __name__ == '__MAIN__':
# Array trié
trid_arr = [0,4,7,10,14,23,45,47,53]
# longueur du tableau
n = len (trid_arr)
#Element à rechercher
cible = 47
position = binary_search (trid_arr, n, cible)
Si la position != -1:
print (f "élément cible présent à index position")
autre:
print (f "élément cible ne présente pas dans le tableau")

Sortir

Élément 47 présent à l'index 7

Récursif
En récursif au lieu d'utiliser une boucle, nous continuons à appeler la fonction encore et encore jusqu'à ce que la condition de base soit satisfaite

def binary_search (arr, gauche, droite, cible):
#Base Condition
Si RightTarget:
return binary_search (arr, gauche, milieu-1, cible)
# Si l'élément cible est plus petit que l'élément central
autre:
return binary_search (arr, middle + 1, à droite, cible)
Si __name__ == '__MAIN__':
# Array trié
trid_arr = [0,4,7,10,14,23,45,47,53]
gauche = 0
droite = Len (trid_arr) -1
#Element à rechercher
cible = 47
position = binary_search (trid_arr, gauche, droite, cible)
Si la position != -1:
print (f "élément cible présent à index position")
autre:
print (f "élément cible ne présente pas dans le tableau")

Sortir

L'élément 90 n'est pas présent dans le tableau

Complexité

La recherche binaire a une complexité temporelle de O (log n), où n le nombre d'éléments présents dans le tableau.

La recherche binaire a une complexité spatiale d'O (1) parce que, dans l'algorithme, nous effectuons la recherche sur place.

Conclusion

La recherche binaire est l'un des algorithmes de recherche les meilleurs et efficaces. Le temps et la complexité spatiale de la recherche binaire sont également très faibles; La seule condition préalable de la recherche binaire est que le tableau d'entrée doit être trié par ordre croissant.