Vi deler en samling av elementer i to halvdeler i binært søk for å redusere antallet direkte sammenligninger som trengs for å oppdage et element. Det er imidlertid ett krav: arrayets elementer må sorteres på forhånd.
Binært søk
De Binært søk Metoden finner indeksen til et bestemt listemedlem. Det er blant de mest populære og raskeste algoritmene. For at prosedyren for binært søk skal fungere, bør oppføringene i listen sorteres.
Binært søk er en mer effektiv søketeknikk for å finne et elements indeks enn Lineært søk siden vi ikke trenger å undersøke hver listeindeks.
Hele operasjonen til den binære søkealgoritmen kan oppsummeres i følgende trinn:
- Finn midtelementet i den sorterte matrisen.
- Foreta en sammenligning mellom elementet som skal lokaliseres og midtelementet.
- Hvis dette elementet er lik midtelementet i den gitte listen, returneres indeksen til midtelementet. Ellers vil algoritmen sammenligne elementet med elementet i midten.
- Nå, hvis elementet som skal lokaliseres er større enn det midterste elementet på listen, vil det bli sammenlignet med høyre halvdel av listen, dvs. elementer etter midtindeksen.
- Eller hvis elementet er mindre enn elementet i midten av listen, vil det sammenlignes med bare venstre halvdel av listen, dvs. elementer før midtindeksen.
Rekursivt binært søk
Binært søk innebærer kontinuerlig å dele søkeintervallet i 2 like deler for å oppdage et element i en sortert matrise, og tilbakevendende binærsøk innebærer å bryte ned hele binære søkeprosedyren i mindre problemer. Et rekursivt binært søk er rekursjonssvaret på et binært søk.
Følgende er egenskapene som alle rekursive løsninger må oppfylle:
- En base case er nødvendig for en rekursiv tilnærming.
- Det må være et rekursivt testtilfelle i en rekursiv tilnærming.
- En rekursiv tilnærming må komme nærmere basistilfellet.
Den laveste underavdelingen av et komplisert problem er representert av et grunntilfelle, som er et endelig tilfelle. Så for å utføre det binære søket etter rekursiv metode, må algoritmen vår inneholde et grunntilfelle og et rekursivt tilfelle, med det rekursive tilfellet videre til grunntilfellet. Ellers ville prosessen aldri fullført og resultere i en endeløs loop.
Den binære søketeknikken reduserer tiden det tar å finne et spesifikt element i en sortert matrise. Den binære søkemetoden implementeres ofte iterativt, men vi kan også implementere den rekursivt ved å bryte den ned i mindre biter.
Kode
#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!')
Produksjon:
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
Rekursjon er en ekstremt kraftig programmerings- og problemløsningsteknikk. Vi kan bruke den til å evaluere og utføre en rekke algoritmer, alt fra enkle iterative problemer til kompliserte tilbakesporingsproblemer. I denne opplæringen så vi på å bruke Python-språket for å lage den rekursive binære søkemetoden.