Kolekci položek jsme v Binary Search rozdělili na dvě poloviny, abychom snížili počet přímých porovnání potřebných k objevení prvku. Existuje však jeden požadavek: položky pole musí být předem seřazeny.

Binární vyhledávání

The Binární vyhledávání Metoda vyhledá index určitého člena seznamu. Patří mezi nejpopulárnější a nejrychlejší algoritmy. Aby procedura Binary Search fungovala, měly by být položky v seznamu seřazeny.

Binární vyhledávání je efektivnější vyhledávací technika pro nalezení indexu prvku než Lineární vyhledávání protože nemusíme zkoumat každý index seznamu.

Celá operace Binary Search Algorithm může být shrnuta do následujících kroků:

• Vyhledejte prostřední prvek v seřazeném poli.
• Proveďte srovnání mezi prvkem, který má být umístěn, a prostředním prvkem.
• Pokud je tento prvek roven prostřednímu prvku daného seznamu, vrátí se index prostředního prvku. Jinak algoritmus porovná prvek s položkou uprostřed.
• Nyní, pokud je prvek, který má být umístěn, větší než prostřední položka seznamu, bude porovnán s pravou polovinou seznamu, tj. prvky za prostředním indexem.
• Nebo pokud je prvek menší než prvek uprostřed seznamu, bude porovnán pouze s levou polovinou seznamu, tj. prvky před prostředním indexem.

Rekurzivní binární vyhledávání

Binární vyhledávání znamená neustálé rozdělování intervalu vyhledávání na 2 stejné části, aby se objevil prvek v setříděném poli, a opakované binární vyhledávání znamená rozdělit celý postup binárního vyhledávání na menší problémy. Rekurzivní binární vyhledávání je rekurzivní odpovědí na binární vyhledávání.

Toto jsou vlastnosti, které musí plně rekurzivní řešení splňovat:

1. Pro rekurzivní přístup je vyžadován základní případ.
2. V rekurzivním přístupu musí existovat rekurzivní testovací případ.
3. Rekurzivní přístup se musí přiblížit základnímu případu.

Nejnižší poddělení komplikovaného problému představuje základní případ, který je konečným případem. Abychom tedy mohli provést binární vyhledávání rekurzivní metodou, náš algoritmus musí obsahovat základní případ a rekurzivní případ, přičemž rekurzivní případ postupuje do základního případu. Jinak by proces nikdy neskončil a výsledkem by byla nekonečná smyčka.

Technika binárního vyhledávání zkracuje čas potřebný k nalezení konkrétního prvku uvnitř setříděného pole. Metoda binárního vyhledávání je často implementována iterativně, ale můžeme ji implementovat také rekurzivně tak, že ji rozložíme na menší části.

Kód

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

Výstup:

java jinak pokud

 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 

Rekurze je extrémně výkonná technika programování a řešení problémů. Můžeme jej použít k vyhodnocení a provedení různých algoritmů, od jednoduchých iteračních problémů až po složité problémy se zpětným sledováním. V tomto tutoriálu jsme se podívali na použití jazyka Python k vytvoření metody rekurzivního binárního vyhledávání.