We hebben een verzameling items in Binary Search in twee helften gesplitst om het aantal directe vergelijkingen dat nodig is om een ​​element te ontdekken te verminderen. Er is echter één vereiste: de items in de array moeten vooraf worden gesorteerd.

Binaire zoekopdracht

De Binaire zoekopdracht Methode lokaliseert de index van een bepaald lijstlid. Het is een van de meest populaire en snelste algoritmen. Om de binaire zoekprocedure te laten werken, moeten de vermeldingen in de lijst worden gesorteerd.

Binaire zoekopdracht is een efficiëntere zoektechniek voor het lokaliseren van de index van een element dan Lineair zoeken omdat we niet elke lijstindex hoeven te onderzoeken.

De hele werking van het binaire zoekalgoritme kan in de volgende stappen worden samengevat:

• Zoek het middelste element in de gesorteerde array.
• Maak een vergelijking tussen het te plaatsen element en het middelste element.
• Als dat element gelijk is aan het middelste element van de gegeven lijst, wordt de index van het middelste element geretourneerd. Anders vergelijkt het algoritme het element met het item in het midden.
• Als het te lokaliseren element nu groter is dan het middelste item van de lijst, zal het worden vergeleken met de rechterhelft van de lijst, d.w.z. elementen na de middelste index.
• Of als het element kleiner is dan het element in het midden van de lijst, dan wordt het alleen vergeleken met de linkerhelft van de lijst, dat wil zeggen met elementen vóór de middelste index.

Recursief binair zoeken

Binair zoeken houdt in dat het zoekinterval voortdurend in twee gelijke delen wordt verdeeld om een ​​element in een gesorteerde array te ontdekken, en herhaaldelijk binair zoeken houdt in dat de volledige binaire zoekprocedure in kleinere problemen wordt opgedeeld. Een recursieve binaire zoekopdracht is het recursieantwoord op een binaire zoekopdracht.

Hieronder volgen de kenmerken waaraan volledig recursieve oplossingen moeten voldoen:

1. Voor een recursieve benadering is een basisscenario vereist.
2. Bij een recursieve benadering moet er sprake zijn van een recursieve testcase.
3. Een recursieve benadering moet dichter bij het basisscenario komen.

De laagste onderverdeling van een ingewikkeld probleem wordt weergegeven door een basisgeval, dat een eindgeval is. Om de binaire zoekopdracht via de recursieve methode uit te voeren, moet ons algoritme dus een basisgeval en een recursief geval bevatten, waarbij het recursieve geval doorgaat naar het basisgeval. Anders zou het proces nooit eindigen en resulteren in een eindeloze lus.

De binaire zoektechniek verkort de tijd die nodig is om een ​​specifiek element binnen een gesorteerde array te vinden. De binaire zoekmethode wordt vaak iteratief geïmplementeerd, maar we kunnen deze ook recursief implementeren door deze in kleinere stukken op te splitsen.

Code

 #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!') 

Uitgang:

 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 

Recursie is een uiterst krachtige programmeer- en probleemoplossende techniek. We kunnen het gebruiken om een ​​verscheidenheid aan algoritmen te evalueren en uit te voeren, variërend van eenvoudige iteratieve problemen tot ingewikkelde backtracking-problemen. In deze zelfstudie hebben we gekeken naar het gebruik van de Python-taal om de recursieve binaire zoekmethode te maken.

int in tekenreeks