Ce didacticiel apprendra comment appliquer un algorithme de recherche binaire à l'aide de Python pour trouver la position d'index d'un élément dans la liste donnée.
Introduction
Une recherche binaire est un algorithme permettant de trouver un élément particulier dans la liste. Supposons que nous ayons une liste de milliers d’éléments et que nous devions obtenir la position d’index d’un élément particulier. Nous pouvons trouver très rapidement la position d'index de l'élément en utilisant l'algorithme de recherche binaire.
Il existe de nombreux algorithmes de recherche, mais la recherche binaire est la plus populaire d'entre eux.
bash divisé en chaîne
Les éléments de la liste doivent être triés pour appliquer l'algorithme de recherche binaire. Si les éléments ne sont pas triés, triez-les d'abord.
Comprenons le concept de recherche binaire.
Concept de recherche binaire
Dans l'algorithme de recherche binaire, nous pouvons trouver la position de l'élément en utilisant les méthodes suivantes.
- Méthode récursive
- Méthode itérative
La technique de l’approche diviser pour mieux régner est suivie de la méthode récursive. Dans cette méthode, une fonction est appelée encore et encore jusqu'à ce qu'elle trouve un élément dans la liste.
Un ensemble d'instructions est répété plusieurs fois pour trouver la position d'index d'un élément dans la méthode itérative. Le alors que la boucle est utilisée pour accomplir cette tâche.
La recherche binaire est plus efficace que la recherche linéaire car nous n'avons pas besoin de rechercher chaque index de liste. La liste doit être triée pour obtenir l'algorithme de recherche binaire.
Implémentons étape par étape la recherche binaire.
Nous avons une liste triée d’éléments et nous recherchons la position d’index de 45.
[12, 24, 32, 39, 45, 50, 54]
Nous définissons donc deux pointeurs dans notre liste. Un pointeur est utilisé pour désigner la plus petite valeur appelée faible et le deuxième pointeur est utilisé pour désigner la valeur la plus élevée appelée haut .
Ensuite, nous calculons la valeur de milieu élément dans le tableau.
mid = (low+high)/2 Here, the low is 0 and the high is 7. mid = (0+7)/2 mid = 3 (Integer)
Maintenant, nous allons comparer l'élément recherché à la valeur médiane de l'index. Dans ce cas, 32 n'est pas égal à Quatre cinq. Nous devons donc effectuer une comparaison plus approfondie pour trouver l'élément.
Si le nombre que nous recherchons est égal au milieu. Puis reviens milieu sinon, passez à la comparaison plus approfondie.
Le nombre à rechercher est supérieur au milieu nombre, nous comparons le n avec l'élément du milieu des éléments sur le côté droit de milieu et réglé bas à bas = milieu + 1.
Sinon, comparez le n avec le élément central des éléments sur le côté gauche de milieu Et mettre haut à haut = milieu - 1.
Répétez jusqu'à ce que le numéro que nous recherchons soit trouvé.
Implémenter une recherche binaire en Python
Tout d’abord, nous implémentons une recherche binaire avec la méthode itérative. Nous allons répéter un ensemble d’instructions et parcourir chaque élément de la liste. Nous trouverons la valeur médiane jusqu'à ce que la recherche soit terminée.
Comprenons le programme suivant de la méthode itérative.
comment exécuter le script sous Linux
Implémentation Python
# Iterative Binary Search Function method Python Implementation # It returns index of n in given list1 if present, # else returns -1 def binary_search(list1, n): low = 0 high = len(list1) - 1 mid = 0 while low <= 1 2 high: # for get integer result mid="(high" + low) check if n is present at list1[mid] n: high="mid" - smaller, compared to the left of else: return element was not in list, -1 initial list1 24, 32, 39, 45, 50, 54] function call n) !="-1:" print('element index', str(result)) list1') < pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 4 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above program -</p> <ul> <li>We have created a function called <strong>binary_search()</strong> function which takes two arguments - a list to sorted and a number to be searched.</li> <li>We have declared two variables to store the lowest and highest values in the list. The low is assigned initial value to 0, <strong>high</strong> to <strong>len(list1)</strong> - 1 and mid as 0.</li> <li>Next, we have declared the <strong>while</strong> loop with the condition that the <strong>lowest</strong> is equal and smaller than the <strong>highest</strong> The while loop will iterate if the number has not been found yet.</li> <li>In the while loop, we find the mid value and compare the index value to the number we are searching for.</li> <li>If the value of the mid-index is smaller than <strong>n</strong> , we increase the mid value by 1 and assign it to The search moves to the left side.</li> <li>Otherwise, decrease the mid value and assign it to the <strong>high</strong> . The search moves to the right side.</li> <li>If the n is equal to the mid value then return <strong>mid</strong> .</li> <li>This will happen until the <strong>low</strong> is equal and smaller than the <strong>high</strong> .</li> <li>If we reach at the end of the function, then the element is not present in the list. We return -1 to the calling function.</li> </ul> <p>Let's understand the recursive method of binary search.</p> <h2>Recursive Binary Search</h2> <p>The recursion method can be used in the binary search. In this, we will define a recursive function that keeps calling itself until it meets the condition.</p> <p>Let's understand the above program using the recursive function.</p> <h3>Python Program</h3> <pre> # Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print('Element is present at index', str(res)) else: print('Element is not present in list1') </pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 2 </pre> <p> <strong>Explanation</strong> </p> <p>The above program is similar to the previous program. We declared a recursive function and its base condition. The condition is the lowest value is smaller or equal to the highest value.</p> <ul> <li>We calculate the middle number as in the last program.</li> <li>We have used the <strong>if</strong> statement to proceed with the binary search.</li> <li>If the middle value equal to the number that we are looking for, the middle value is returned.</li> <li>If the middle value is less than the value, we are looking then our recursive function <strong>binary_search()</strong> again and increase the mid value by one and assign to low.</li> <li>If the middle value is greater than the value we are looking then our recursive function <strong>binary_search()</strong> again and decrease the mid value by one and assign it to low.</li> </ul> <p>In the last part, we have written our main program. It is the same as the previous program, but the only difference is that we have passed two parameters in the <strong>binary_search()</strong> function.</p> <p>This is because we can't assign the initial values to the low, high and mid in the recursive function. Every time the recursive is called the value will be reset for those variables. That will give the wrong result.</p> <h2>Complexity</h2> <p>The complexity of the binary search algorithm is <strong>O(1)</strong> for the best case. This happen if the element that element we are looking find in the first comparison. The <strong>O(logn)</strong> is the worst and the average case complexity of the binary search. This depends upon the number of searches are conducted to find the element that we are looking for.</p> <h2>Conclusion</h2> <p>A binary search algorithm is the most efficient and fast way to search an element in the list. It skips the unnecessary comparison. As the name suggests, the search is divided into two parts. It focuses on the side of list, which is close to the number that we are searching.</p> <p>We have discussed both methods to find the index position of the given number.</p> <hr></=> Explication:
Dans le programme ci-dessus -
- Nous avons créé une fonction appelée recherche binaire() fonction qui prend deux arguments - une liste à trier et un nombre à rechercher.
- Nous avons déclaré deux variables pour stocker les valeurs les plus basses et les plus élevées de la liste. Le bas se voit attribuer la valeur initiale à 0, haut à len (liste1) - 1 et milieu à 0.
- Ensuite, nous avons déclaré le alors que boucle à condition que le le plus bas est égal et plus petit que le le plus élevé La boucle while sera itérée si le numéro n'a pas encore été trouvé.
- Dans la boucle while, nous trouvons la valeur moyenne et comparons la valeur de l'index au nombre que nous recherchons.
- Si la valeur de l'indice médian est inférieure à n , nous augmentons la valeur médiane de 1 et l'attribuons à La recherche se déplace vers la gauche.
- Sinon, diminuez la valeur moyenne et attribuez-la au haut . La recherche se déplace vers la droite.
- Si n est égal à la valeur moyenne, retournez milieu .
- Cela se produira jusqu'à ce que faible est égal et plus petit que le haut .
- Si on arrive à la fin de la fonction, alors l'élément n'est pas présent dans la liste. Nous renvoyons -1 à la fonction appelante.
Comprenons la méthode récursive de recherche binaire.
Recherche binaire récursive
La méthode de récursivité peut être utilisée dans la recherche binaire. En cela, nous définirons une fonction récursive qui continue de s'appeler jusqu'à ce qu'elle remplisse la condition.
Comprenons le programme ci-dessus en utilisant la fonction récursive.
Programme Python
# Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print('Element is present at index', str(res)) else: print('Element is not present in list1')
Sortir:
Element is present at index 2
Explication
Le programme ci-dessus est similaire au programme précédent. Nous avons déclaré une fonction récursive et sa condition de base. La condition est que la valeur la plus basse soit inférieure ou égale à la valeur la plus élevée.
- Nous calculons le nombre du milieu comme dans le dernier programme.
- Nous avons utilisé le si instruction pour procéder à la recherche binaire.
- Si la valeur médiane est égale au nombre que nous recherchons, la valeur médiane est renvoyée.
- Si la valeur médiane est inférieure à la valeur, on regarde alors notre fonction récursive recherche binaire() à nouveau et augmentez la valeur moyenne de un et attribuez-la à faible.
- Si la valeur moyenne est supérieure à la valeur recherchée alors notre fonction récursive recherche binaire() encore une fois et diminuez la valeur moyenne de un et attribuez-la à faible.
Dans la dernière partie, nous avons écrit notre programme principal. C'est la même chose que le programme précédent, mais la seule différence est que nous avons passé deux paramètres dans le recherche binaire() fonction.
En effet, nous ne pouvons pas attribuer les valeurs initiales aux valeurs basse, haute et moyenne dans la fonction récursive. Chaque fois que la récursive est appelée, la valeur sera réinitialisée pour ces variables. Cela donnera un mauvais résultat.
Complexité
La complexité de l'algorithme de recherche binaire est O(1) pour le meilleur des cas. Cela se produit si l'élément que nous recherchons trouve dans la première comparaison. Le O (connexion) est le pire et la complexité moyenne des cas de recherche binaire. Cela dépend du nombre de recherches effectuées pour trouver l'élément que nous recherchons.
Conclusion
Un algorithme de recherche binaire est le moyen le plus efficace et le plus rapide de rechercher un élément dans la liste. Cela évite la comparaison inutile. Comme son nom l’indique, la recherche est divisée en deux parties. Il se concentre sur le côté de la liste, qui est proche du numéro que nous recherchons.
javatable
Nous avons discuté des deux méthodes pour trouver la position d'index du nombre donné.