Jaamme kokoelman kohteita kahteen puolikkaaseen Binary Searchissa vähentääksemme elementin löytämiseen tarvittavien suorien vertailujen määrää. Yksi vaatimus kuitenkin on: taulukon kohteet on lajiteltava etukäteen.
Binäärihaku
The Binäärihaku Method paikantaa tietyn listan jäsenen indeksin. Se on yksi suosituimmista ja nopeimmista algoritmeista. Jotta binaarihakutoiminto toimisi, luettelon merkinnät tulee lajitella.
merkkijonon muuntaminen int
Binäärihaku on tehokkaampi hakutekniikka elementin indeksin paikantamiseen kuin Lineaarinen haku koska meidän ei tarvitse tutkia jokaista luettelohakemistoa.
Binäärihakualgoritmin koko toiminta voidaan tiivistää seuraaviin vaiheisiin:
- Etsi keskimmäinen elementti lajitetusta taulukosta.
- Tee vertailu sijoitettavan elementin ja keskielementin välillä.
- Jos tämä elementti on yhtä suuri kuin annetun luettelon keskimmäinen elementti, keskimmäisen elementin indeksi palautetaan. Muussa tapauksessa algoritmi vertaa elementtiä keskellä olevaan kohteeseen.
- Jos nyt etsittävä elementti on suurempi kuin listan keskimmäinen kohde, sitä verrataan listan oikeaan puoliskoon eli keskiindeksin jälkeisiin elementteihin.
- Tai jos elementti on pienempi kuin listan keskellä oleva elementti, sitä verrataan vain listan vasempaan puoliskoon eli elementteihin ennen keskimmäistä indeksiä.
Rekursiivinen binaarihaku
Binäärihaku tarkoittaa, että hakuväli jaetaan jatkuvasti kahteen yhtä suureen osaan elementin löytämiseksi lajitetusta taulukosta, ja toistuva binäärihaku edellyttää koko binaarihaun hajottamista pienempiin ongelmiin. Rekursiivinen binäärihaku on rekursiovastaus binäärihakuun.
Seuraavat ovat ominaisuudet, jotka täysin rekursiivisten ratkaisujen on täytettävä:
- Rekursiivista lähestymistapaa varten tarvitaan perustapaus.
- Rekursiivisessa lähestymistavassa täytyy olla rekursiivinen testitapaus.
- Rekursiivisen lähestymistavan on päästävä lähemmäksi perustapausta.
Monimutkaisen ongelman alinta alajakoa edustaa perustapaus, joka on lopullinen tapaus. Joten binäärihaun suorittamiseksi rekursiivisella menetelmällä algoritmimme tulee sisältää perustapaus ja rekursiivinen tapaus, jolloin rekursiivinen tapaus etenee perustapaukseen. Muuten prosessi ei koskaan päättyisi ja johtaisi loputtomaan silmukkaan.
Binäärihakutekniikka vähentää aikaa, joka kuluu tietyn elementin löytämiseen lajitellun taulukon sisältä. Binäärihakumenetelmä toteutetaan usein iteratiivisesti, mutta voimme toteuttaa sen myös rekursiivisesti jakamalla sen pienempiin osiin.
Koodi
jos-else 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!')
Lähtö:
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
Rekursio on erittäin tehokas ohjelmointi- ja ongelmanratkaisutekniikka. Voimme käyttää sitä erilaisten algoritmien arvioimiseen ja suorittamiseen yksinkertaisista iteratiivisista ongelmista monimutkaisiin paluuongelmiin. Tässä opetusohjelmassa tarkastelimme Python-kielen käyttöä rekursiivisen binaarihakumenetelmän luomiseen.