Zbirko elementov v binarnem iskanju razdelimo na dve polovici, da zmanjšamo število neposrednih primerjav, potrebnih za odkrivanje elementa. Vendar pa obstaja ena zahteva: elemente matrike je treba predhodno razvrstiti.
Binarno iskanje
The Binarno iskanje Metoda poišče indeks določenega člana seznama. Je med najbolj priljubljenimi in najhitrejšimi algoritmi. Da bi postopek binarnega iskanja deloval, morajo biti vnosi na seznamu razvrščeni.
hashmap java
Binarno iskanje je učinkovitejša tehnika iskanja za iskanje indeksa elementa kot Linearno iskanje saj nam ni treba pregledati vsakega indeksa seznama.
Celotno operacijo algoritma binarnega iskanja je mogoče povzeti v naslednjih korakih:
- Poiščite srednji element v razvrščeni matriki.
- Primerjajte element, ki ga želite locirati, in srednji element.
- Če je ta element enak srednjemu elementu danega seznama, se vrne indeks srednjega elementa. V nasprotnem primeru bo algoritem primerjal element z elementom na sredini.
- Zdaj, če je element, ki ga želite locirati, večji od srednjega elementa seznama, se bo primerjal z desno polovico seznama, tj. elementi za srednjim indeksom.
- Če pa je element manjši od elementa na sredini seznama, bo primerjan le z levo polovico seznama, tj. elementi pred srednjim indeksom.
Rekurzivno binarno iskanje
Binarno iskanje pomeni nenehno delitev iskalnega intervala na 2 enaka dela, da se odkrije element v razvrščeni matriki, ponavljajoče se binarno iskanje pa vključuje razčlenitev celotnega postopka binarnega iskanja na manjše težave. Rekurzivno binarno iskanje je rekurzivni odgovor na binarno iskanje.
Sledijo značilnosti, ki jih morajo izpolnjevati vserekurzivne rešitve:
- Za rekurzivni pristop je potreben osnovni primer.
- V rekurzivnem pristopu mora obstajati rekurziven testni primer.
- Rekurzivni pristop se mora približati osnovnemu primeru.
Najnižjo podrazdelitev zapletenega problema predstavlja osnovni primer, ki je končni primer. Za izvedbo binarnega iskanja z rekurzivno metodo mora naš algoritem vsebovati osnovni in rekurzivni primer, pri čemer rekurzivni primer napreduje v osnovni primer. V nasprotnem primeru se postopek ne bi nikoli končal in povzročil bi neskončno zanko.
Tehnika binarnega iskanja skrajša čas, potreben za iskanje določenega elementa znotraj razvrščenega niza. Metoda binarnega iskanja se pogosto izvaja iterativno, lahko pa jo izvajamo tudi rekurzivno, tako da jo razdelimo na manjše dele.
Koda
java konec za zanko
#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!')
Izhod:
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
Rekurzija je izjemno zmogljiva tehnika programiranja in reševanja problemov. Lahko ga uporabimo za ovrednotenje in izvajanje različnih algoritmov, od preprostih iterativnih težav do zapletenih težav s sledenjem nazaj. V tej vadnici smo si ogledali uporabo jezika Python za ustvarjanje metode rekurzivnega binarnega iskanja.