Mēs sadalām vienumu kolekciju divās daļās binārajā meklēšanā, lai samazinātu elementa atklāšanai nepieciešamo tiešo salīdzinājumu skaitu. Tomēr ir viena prasība: masīva vienumi ir jāsakārto iepriekš.
Binārā meklēšana
The Binārā meklēšana Metode atrod noteikta saraksta dalībnieka indeksu. Tas ir viens no populārākajiem un ātrākajiem algoritmiem. Lai binārās meklēšanas procedūra darbotos, saraksta ieraksti ir jāsakārto.
attēls kā fons css
Binārā meklēšana ir efektīvāks meklēšanas paņēmiens elementa indeksa atrašanai nekā Lineārā meklēšana jo mums nav jāpārbauda katrs saraksta indekss.
Visu binārās meklēšanas algoritma darbību var apkopot šādās darbībās:
- Atrodiet vidējo elementu sakārtotajā masīvā.
- Veiciet salīdzinājumu starp novietojamo elementu un vidējo elementu.
- Ja šis elements ir vienāds ar dotā saraksta vidējo elementu, tad tiek atgriezts vidējā elementa indekss. Pretējā gadījumā algoritms salīdzinās elementu ar elementu vidū.
- Tagad, ja izvietojamais elements ir lielāks par saraksta vidējo vienumu, tas tiks salīdzināts ar saraksta labo pusi, t.i., elementiem aiz vidējā rādītāja.
- Vai arī, ja elements ir mazāks par elementu saraksta vidū, tas tiks salīdzināts tikai ar saraksta kreiso pusi, t.i., elementiem pirms vidējā rādītāja.
Rekursīvā binārā meklēšana
Binārā meklēšana nozīmē nepārtrauktu meklēšanas intervāla sadalīšanu 2 vienādās daļās, lai atrastu elementu sakārtotā masīvā, un atkārtota binārā meklēšana ietver visas binārās meklēšanas procedūras sadalīšanu mazākos jautājumos. Rekursīvā binārā meklēšana ir rekursijas atbilde uz bināro meklēšanu.
Tālāk ir norādītas īpašības, kurām jāatbilst rekursīvajiem risinājumiem:
- Rekursīvai pieejai ir nepieciešams bāzes gadījums.
- Rekursīvajā pieejā ir jābūt rekursīvam testa gadījumam.
- Rekursīvajai pieejai ir jātuvojas bāzes gadījumam.
Sarežģītas problēmas zemāko apakšnodaļu attēlo bāzes gadījums, kas ir galīgais gadījums. Tātad, lai veiktu bināro meklēšanu ar rekursīvo metodi, mūsu algoritmā ir jāietver pamata gadījums un rekursīvs gadījums, rekursīvajam gadījumam pārejot uz bāzes gadījumu. Pretējā gadījumā process nekad netiktu pabeigts un radītu nebeidzamu cilpu.
Binārās meklēšanas tehnika samazina laiku, kas nepieciešams, lai atrastu noteiktu elementu sakārtotā masīvā. Binārā meklēšanas metode bieži tiek ieviesta iteratīvi, taču mēs varam to ieviest arī rekursīvi, sadalot to mazākās daļās.
Kods
faktoriāls 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!')
Izvade:
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 ir ārkārtīgi spēcīgs programmēšanas un problēmu risināšanas paņēmiens. Mēs varam to izmantot, lai novērtētu un izpildītu dažādus algoritmus, sākot no vienkāršām iteratīvām problēmām līdz sarežģītām atpakaļsekošanas problēmām. Šajā apmācībā mēs apskatījām Python valodas izmantošanu, lai izveidotu rekursīvo bināro meklēšanas metodi.