Dvejetainėje paieškoje elementų kolekciją padalijome į dvi dalis, kad sumažintume tiesioginių palyginimų, reikalingų elementui atrasti, skaičių. Tačiau yra vienas reikalavimas: masyvo elementai turi būti surūšiuoti iš anksto.

Dvejetainė paieška

The Dvejetainė paieška Metodas nustato tam tikro sąrašo nario indeksą. Tai vienas iš populiariausių ir greičiausių algoritmų. Kad dvejetainės paieškos procedūra veiktų, sąrašo įrašai turi būti surūšiuoti.

Dvejetainė paieška yra efektyvesnė paieškos technika elemento indekso vietai nustatyti nei Linijinė paieška nes mes neturime nagrinėti kiekvieno sąrašo indekso.

Visa dvejetainio paieškos algoritmo operacija gali būti apibendrinta taip:

• Suraskite vidurinį elementą surūšiuotame masyve.
• Palyginkite elementą, kurį reikia įdėti, ir vidurinį elementą.
• Jei tas elementas yra lygus viduriniajam nurodyto sąrašo elementui, tada grąžinamas vidurinio elemento indeksas. Priešingu atveju algoritmas palygins elementą su elementu viduryje.
• Dabar, jei turimas elementas yra didesnis nei vidurinis sąrašo elementas, jis bus lyginamas su dešiniąja sąrašo puse, t. y. elementais po vidurinio indekso.
• Arba jei elementas yra mažesnis už elementą sąrašo viduryje, jis bus lyginamas tik su kairiąja sąrašo puse, t. y. elementais, esančiais prieš vidurinį indeksą.

Rekursinė dvejetainė paieška

Dvejetainė paieška reiškia nuolatinį paieškos intervalo padalijimą į 2 lygias dalis, kad būtų atrastas elementas surūšiuotame masyve, o pasikartojanti dvejetainė paieška reiškia visos dvejetainės paieškos procedūros suskaidymą į smulkesnes problemas. Rekursinė dvejetainė paieška yra dvejetainės paieškos rekursinis atsakymas.

Toliau pateikiamos charakteristikos, kurias turi atitikti visi rekursiniai sprendimai:

1. Rekursiniam metodui reikalingas bazinis atvejis.
2. Taikant rekursinį metodą, turi būti rekursinis bandymo atvejis.
3. Rekursyvus metodas turi priartėti prie bazinio atvejo.

Žemiausias sudėtingos problemos poskyris yra bazinis atvejis, kuris yra galutinis atvejis. Taigi, norint atlikti dvejetainę paiešką rekursiniu metodu, mūsų algoritme turi būti bazinis ir rekursinis atvejis, o rekursinis atvejis pereina į bazinį. Priešingu atveju procesas niekada nesibaigs ir atsiras begalinis ciklas.

Dvejetainė paieškos technika sumažina laiką, kurio reikia norint rasti konkretų elementą surūšiuotame masyve. Dvejetainis paieškos metodas dažnai įgyvendinamas iteratyviai, tačiau galime jį įgyvendinti ir rekursyviai, suskaidydami jį į mažesnes dalis.

Kodas

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

Išvestis:

 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 

Rekursija yra labai galinga programavimo ir problemų sprendimo technika. Galime jį naudoti norėdami įvertinti ir vykdyti įvairius algoritmus, pradedant nuo paprastų iteracinių problemų ir baigiant sudėtingomis atšaukimo problemomis. Šioje pamokoje apžvelgėme Python kalbos naudojimą kurdami rekursinį dvejetainį paieškos metodą.

medžio ir grafų teorija