Complexité temporelle de Recherche binaire est O (log n) , où n est le nombre d'éléments dans le tableau. Il divise le tableau en deux à chaque étape. Complexité spatiale est O(1) car il utilise une quantité constante d’espace supplémentaire.

fmoviez

Exemple d'algorithme de recherche binaire

Les complexités temporelles et spatiales de l’algorithme de recherche binaire sont mentionnées ci-dessous.

Complexité temporelle de Algorithme de recherche binaire :

Complexité temporelle dans le meilleur des cas de l'algorithme de recherche binaire : O(1)

Le meilleur des cas est lorsque l’élément se trouve à l’index central du tableau. Il suffit d'une seule comparaison pour trouver l'élément cible. La meilleure complexité des cas est donc O(1) .

Complexité du temps moyen de l'algorithme de recherche binaire : O (log N)

Considérez le tableau arr[] de longueur N et élément X être trouvé. Il peut y avoir deux cas :

• Cas 1: L'élément est présent dans le tableau
• Cas 2 : L'élément n'est pas présent dans le tableau.

Il y a N Cas1 et 1 Cas2. Donc nombre total de cas = N+1 . Notez maintenant ce qui suit :

• Un élément à l'indice N/2 se trouve dans 1 comparaison
• Les éléments aux indices N/4 et 3N/4 se retrouvent dans 2 comparaisons.
• Les éléments aux indices N/8, 3N/8, 5N/8 et 7N/8 peuvent être trouvés dans 3 comparaisons et ainsi de suite.

Sur cette base, nous pouvons conclure que les éléments qui nécessitent :

concaténer la chaîne Java

• 1 comparaison = 1
• 2 comparaisons = 2
• 3 comparaisons = 4
• X comparaisons = 2 ^x-1 où X appartient à la gamme [1, logN] car comparaisons maximales = temps maximum N peut être réduit de moitié = comparaisons maximales pour atteindre le 1er élément = logN.

Donc, des comparaisons totales
= 1*(éléments nécessitant 1 comparaisons) + 2*(éléments nécessitant 2 comparaisons) + . . . + logN*(éléments nécessitant des comparaisons logN)
= 1*1 + 2*2 + 3*4 + . . . + logN * (2^logN-1)
= 2^calme* (logN – 1) + 1
= N * (logN – 1) + 1

Nombre total de cas = N+1 .

Par conséquent, la complexité moyenne = ( N*(logN – 1) + 1)/N+1 = N*logN / (N+1) + 1/(N+1) . Ici le terme dominant est N*logN/(N+1) qui est approximativement calme . La complexité moyenne des cas est donc O (logN)

dérivé partiel du latex

Dans le pire des cas, complexité temporelle de l'algorithme de recherche binaire : O (log N)

Le pire des cas sera lorsque l’élément est présent en première position. Comme on le voit dans le cas moyen, la comparaison requise pour atteindre le premier élément est calme . La complexité temporelle pour le pire des cas est donc O (logN) .

Complexité spatiale auxiliaire de l'algorithme de recherche binaire

Le complexité de l'espace auxiliaire de la Algorithme de recherche binaire est O(1) , ce qui signifie qu'il nécessite une quantité constante d'espace supplémentaire quelle que soit la taille du tableau d'entrée. En effet, la recherche binaire est un algorithme itératif qui ne nécessite aucune structure de données supplémentaire ni récursion qui augmente avec la taille d'entrée. Cependant, nous pouvons également implémenter la recherche binaire de manière récursive.