V binárnom vyhľadávaní sme rozdelili kolekciu položiek na dve polovice, aby sme znížili počet priamych porovnaní potrebných na objavenie prvku. Existuje však jedna požiadavka: položky poľa musia byť vopred zoradené.

java mapa

Binárne vyhľadávanie

The Binárne vyhľadávanie Metóda nájde index určitého člena zoznamu. Patrí medzi najpopulárnejšie a najrýchlejšie algoritmy. Aby postup Binary Search fungoval, položky v zozname by mali byť zoradené.

Binárne vyhľadávanie je efektívnejšia vyhľadávacia technika na nájdenie indexu prvku ako Lineárne vyhľadávanie pretože nemusíme skúmať každý index zoznamu.

Celá operácia Binárneho vyhľadávacieho algoritmu môže byť zhrnutá do nasledujúcich krokov:

• Nájdite stredný prvok v zoradenom poli.
• Vykonajte porovnanie medzi prvkom, ktorý sa má umiestniť, a stredným prvkom.
• Ak sa tento prvok rovná strednému prvku daného zoznamu, vráti sa index stredného prvku. V opačnom prípade algoritmus porovná prvok s položkou v strede.
• Ak je teraz prvok, ktorý sa má nájsť, väčší ako stredná položka zoznamu, porovná sa s pravou polovicou zoznamu, t. j. prvkami za stredným indexom.
• Alebo ak je prvok menší ako prvok v strede zoznamu, potom sa porovná iba s ľavou polovicou zoznamu, t. j. prvkami pred stredným indexom.

Rekurzívne binárne vyhľadávanie

Binárne vyhľadávanie znamená neustále delenie vyhľadávacieho intervalu na 2 rovnaké časti, aby sa objavil prvok v triedenom poli, a opakované binárne vyhľadávanie znamená rozdelenie kompletného binárneho vyhľadávania na menšie problémy. Rekurzívne binárne vyhľadávanie je odpoveďou rekurzie na binárne vyhľadávanie.

parameter verilog

Nasledovné sú charakteristiky, ktoré musia spĺňať všetky rekurzívne riešenia:

1. Pre rekurzívny prístup je potrebný základný prípad.
2. V rekurzívnom prístupe musí existovať rekurzívny testovací prípad.
3. Rekurzívny prístup sa musí priblížiť k základnému prípadu.

Najnižšie rozdelenie komplikovaného problému predstavuje základný prípad, ktorý je konečným prípadom. Takže, aby sme vykonali binárne vyhľadávanie rekurzívnou metódou, náš algoritmus musí obsahovať základný prípad a rekurzívny prípad, pričom rekurzívny prípad postupuje do základného prípadu. Inak by sa proces nikdy neskončil a výsledkom by bola nekonečná slučka.

Technika binárneho vyhľadávania skracuje čas potrebný na nájdenie konkrétneho prvku v triedenom poli. Metóda binárneho vyhľadávania sa často implementuje iteratívne, ale môžeme ju implementovať aj rekurzívne tak, že ju rozdelíme na menšie časti.

java ako prepísať

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ýkon:

 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 

Rekurzia je mimoriadne výkonná technika programovania a riešenia problémov. Môžeme ho použiť na vyhodnotenie a vykonanie rôznych algoritmov, od jednoduchých iteračných problémov až po komplikované problémy so spätným sledovaním. V tomto návode sme sa zamerali na použitie jazyka Python na vytvorenie metódy rekurzívneho binárneho vyhľadávania.