Nous divisons une collection d'éléments en deux moitiés dans la recherche binaire pour réduire le nombre de comparaisons directes nécessaires pour découvrir un élément. Il y a cependant une condition : les éléments du tableau doivent être triés au préalable.

Recherche binaire

Le Recherche binaire La méthode localise l’index d’un certain membre de la liste. Il fait partie des algorithmes les plus populaires et les plus rapides. Pour que la procédure de recherche binaire fonctionne, les entrées de la liste doivent être triées.

index de la liste

Recherche binaire est une technique de recherche plus efficace pour localiser l'index d'un élément que Recherche linéaire puisque nous n'avons pas besoin d'examiner chaque index de liste.

L'ensemble du fonctionnement de l'algorithme de recherche binaire peut être résumé dans les étapes suivantes :

• Localisez l'élément du milieu dans le tableau trié.
• Faites une comparaison entre l'élément à localiser et l'élément du milieu.
• Si cet élément est égal à l’élément du milieu de la liste donnée, alors l’index de l’élément du milieu est renvoyé. Sinon, l'algorithme comparera l'élément avec l'élément du milieu.
• Désormais, si l'élément à localiser est supérieur à l'élément du milieu de la liste, il sera comparé à la moitié droite de la liste, c'est-à-dire aux éléments après l'index du milieu.
• Ou si l'élément est inférieur à l'élément au milieu de la liste, alors il sera comparé uniquement à la moitié gauche de la liste, c'est-à-dire aux éléments situés avant l'index du milieu.

Recherche binaire récursive

La recherche binaire implique de diviser continuellement l'intervalle de recherche en 2 parties égales pour découvrir un élément dans un tableau trié, et la recherche binaire récurrente implique de décomposer la procédure de recherche binaire complète en problèmes plus petits. Une recherche binaire récursive est la réponse récursive à une recherche binaire.

raccourcis clavier Linux

Voici les caractéristiques que doivent respecter les solutions entièrement récursives :

1. Un cas de base est requis pour une approche récursive.
2. Il doit y avoir un cas de test récursif dans une approche récursive.
3. Une approche récursive doit se rapprocher du cas de base.

La subdivision la plus basse d’un problème complexe est représentée par un cas de base, qui est un cas final. Ainsi, pour effectuer la recherche binaire par méthode récursive, notre algorithme doit contenir un cas de base et un cas récursif, le cas récursif progressant vers le cas de base. Sinon, le processus ne se terminerait jamais et entraînerait une boucle sans fin.

La technique de recherche binaire réduit le temps nécessaire pour trouver un élément spécifique dans un tableau trié. La méthode de recherche binaire est souvent implémentée de manière itérative, mais nous pouvons également la mettre en œuvre de manière récursive en la décomposant en morceaux plus petits.

Code

polymorphisme Java

 #defining a function to execute Binary Search on any given sorted list L. #start is the lowest index of the list being checked at any given time. #end is the highest index of the list being checked at any given time. #item is the item to be searched in the list. def binary_search(L, start, end, item): if end >= start: middle = (start + end) // 2 if L[middle] == item: return middle #middle element is the item to be located #if middle item is greater than the item to be searched, left side of the list will be searched elif L[middle] > item: #starting index will be same but ending index will be the middle of the main list i.e. left half of the list is given in function. return binary_search(L, start, middle - 1, item) else: #if middle item is smaller than the item to be searched, new starting index will be middle of the list i.e. right half of the list. return binary_search(L, middle + 1, end, item) else: #if element is not present in the list return -1 #Drivers code my_list = [ 2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22 ] element_to_search = 6 print('The given list is') print(my_list) index_of_element = binary_search(my_list, 0, len(my_list)-1, element_to_search) if index_of_element != -1: print('Element searched is found at the index ', str(index_of_element), 'of given list') else: print('Element searched is not found in the given list!') 

Sortir:

 The given list is [2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22] Element searched is found at the index 2 of given list 

La récursivité est une technique de programmation et de résolution de problèmes extrêmement puissante. Nous pouvons l'utiliser pour évaluer et exécuter une variété d'algorithmes, allant de simples problèmes itératifs à des problèmes complexes de retour en arrière. Dans ce didacticiel, nous avons examiné l'utilisation du langage Python pour créer la méthode de recherche binaire récursive.