Kolekciju stavki dijelimo na dvije polovice u binarnom pretraživanju kako bismo smanjili broj izravnih usporedbi potrebnih za otkrivanje elementa. Međutim, postoji jedan uvjet: stavke niza moraju se prethodno sortirati.

Binarno pretraživanje

The Binarno pretraživanje Metoda locira indeks određenog člana popisa. Među najpopularnijim je i najbržim algoritmima. Da bi postupak binarnog pretraživanja funkcionirao, unosi na popisu trebaju biti poredani.

lisica protiv vuka

Binarno pretraživanje je učinkovitija tehnika pretraživanja za lociranje indeksa elementa od Linearno pretraživanje budući da ne moramo ispitivati ​​svaki indeks popisa.

Cijela operacija algoritma binarnog pretraživanja može se sažeti u sljedeće korake:

• Pronađite srednji element u sortiranom nizu.
• Napravite usporedbu između elementa koji treba locirati i srednjeg elementa.
• Ako je taj element jednak srednjem elementu zadane liste, vraća se indeks srednjeg elementa. U suprotnom, algoritam će usporediti element sa stavkom u sredini.
• Sada, ako je element koji treba locirati veći od srednje stavke popisa, usporedit će se s desnom polovicom popisa, tj. elementima nakon srednjeg indeksa.
• Ili ako je element manji od elementa na sredini popisa, tada će se uspoređivati ​​samo s lijevom polovicom popisa, tj. elementima prije srednjeg indeksa.

Rekurzivno binarno pretraživanje

Binarno pretraživanje podrazumijeva kontinuirano dijeljenje intervala pretraživanja na 2 jednaka dijela kako bi se otkrio element u sortiranom nizu, a ponavljajuće binarno pretraživanje podrazumijeva rastavljanje cijelog postupka binarnog pretraživanja na manje probleme. Rekurzivno binarno pretraživanje je rekurzivni odgovor na binarno pretraživanje.

Sljedeće su karakteristike koje sve rekurzivna rješenja moraju zadovoljiti:

1. Za rekurzivni pristup potreban je osnovni slučaj.
2. Mora postojati rekurzivni test slučaj u rekurzivnom pristupu.
3. Rekurzivni pristup mora se približiti osnovnom slučaju.

Najniža podpodjela kompliciranog problema predstavljena je osnovnim slučajem, koji je konačni slučaj. Dakle, da bismo izvršili binarno pretraživanje rekurzivnom metodom, naš algoritam mora sadržavati osnovni slučaj i rekurzivni slučaj, pri čemu rekurzivni slučaj napreduje do osnovnog slučaja. Inače proces nikada ne bi završio i rezultirao bi beskonačnom petljom.

Tehnika binarnog pretraživanja smanjuje vrijeme potrebno za pronalazak određenog elementa unutar sortiranog niza. Metoda binarnog pretraživanja često se implementira iterativno, ali je možemo implementirati i rekurzivno razlažući je na manje dijelove.

Kodirati

char tostring java

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

Izlaz:

 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 iznimno moćna tehnika programiranja i rješavanja problema. Možemo ga koristiti za procjenu i izvršavanje raznih algoritama, u rasponu od jednostavnih iterativnih problema do kompliciranih problema povratnog praćenja. U ovom smo vodiču pogledali korištenje jezika Python za stvaranje metode rekurzivnog binarnog pretraživanja.