Lineaarne otsing vs binaarne otsing ja miks peaksime probleemide lahendamisel kasutama binaarset otsingut arendajana

Ütleme nii, et meile antakse sorteeritud n-elemendiline massiiv ja palutakse massiivis antud elementi otsida.

Lihtne ja sirgjooneline meetod on kasutada lineaarset otsingut, mida alustame esimesest elemendist, võrrelda ükshaaval ja leida soovitud element. Näitlikustamiseks öelge, et meil on sorteeritud rida 10 erinevat numbrit väikestest suurteni ja tahame otsida 70:

Halvimal juhul nõuab see, et me selle otsimiseks kogu massiivi läbi jookseksime, st kui element on viimases indeksis. Kui n suureneb m võrra, suureneb ka algoritmi vajaminevate võrdluste / arvamiste arv m-i võrra. Nii võime öelda, et lineaarsel otsingul on O (n) halvimal juhul keerukam käivitusaeg (selle kohta lähemalt allpool).

Kuidas me kasutame binaarset otsingut? Ja mis on binaarne otsing?

Vikipeediast: “Binaarne otsing võrdleb sihtväärtust massiivi keskmise elemendiga; kui need on ebavõrdsed, elimineeritakse pool, milles siht ei saa asuda, ja otsing jätkub ülejäänud poolel, kuni sihtväärtus leitakse. Kui otsing lõpeb sellega, et ülejäänud pool on tühi, siis pole sihtmärki massiivis ”. Joonistame selle välja, et näidata:

Oletame, et meil on sama massiiv ja tahame otsida 70:

Esimesel etapil leiame keskpunkti ja jagage see pooleks, nii et visuaalselt on meil:

Otsime esimesel poolel, 70 pole neis. Seega ignoreerime seda ja teise poole jaoks leiame keskpunkti ja jagage see uuesti pooleks. Ja kuna sellel on paaritu arv elemente, sisaldugem ka mediaanarv (me ei saa ka mediaanarvu lisada, siis ei tee see tegelikku vahet, kuna teine ​​pool lisab selle siis), nii et nüüd on meil:

Uue esimese poole jaoks otsigem 70, see pole ikka veel nende hulgas. Ärgem siis jälle seda ignoreerige, leidke keskpunkt ja jagage see teisel poolel pooleks. Nüüd on meil:

Ja seekord on 70 uues esimeses pooles. Oleme lõpetanud binaarse otsingu.

Nagu näeme, on binaarne otsing palju efektiivsem kui lineaarne otsing, kuna iga kord peame otsima ainult poole järelejäänud massiivist. Tegelikult on binaarsel otsingul ainult O halvimal juhul keerukus (log n) (log tavapäraselt on baas 2). Ja võrrelgem, kui erinevad võivad jõudluses O (n) ja O (log n) olla erinevad - ütleme, et meil on sorteeritud massiiv 1 000 000 elementi:

Halvimal juhul vajab lineaarne otsimine otsinguelemendi leidmiseks 1000000 vist.

Halvimal juhul vajab binaarne otsing logi (1000000) = 19,93 käitusaega, umbes 20 arvamist sihtelemendi leidmiseks.

See on erinevus!

Nüüd võite küsida, miks on binaarsel otsingul O (log n) halvimal juhul keerukas käitamisaeg?

Kokkuvõtteks, vastavalt Vikipeediale: arvutiteaduses kasutatakse suurt O-märget algoritmide klassifitseerimiseks vastavalt sellele, kuidas sisestusmahu kasvades nende tööaeg või ruumivajadus suurenevad. See iseloomustab funktsioone vastavalt nende kasvutempole.

Seega on lineaarse otsimise jaoks massiivi suuruse kasvades kohe ette jõudmine, et halvimal juhul on käitusaja keerukus O (n).

Aga binaarne otsing?

Oletame lihtsuse huvides, et meile antakse massiiv kaheksast elemendist ja üks, mida peame otsima, et „juhtuks”, oleks viimase indeksi juures (halvim olukord). Nii et iga kord jaotame oma massiivi pooleks, kuni meil on jäänud ainult üks element, see on:

Kui me reageerime:

N elemendi puhul olgem refaktor:

Paneme selle logaritmilisse vormi, kuna meil on vaja k:

Ja sellepärast on binaarse otsingu halvim käitamisaeg keeruline (log n). Kõige hämmastavam asi binaarse otsingu puhul on see, et iga kord, kui massiivi suurus kahekordistub, suureneb käitamisaja arvamiste arv ainult ühe võrra!

Mõelge nüüd sellele, kuidas me tavaliselt probleemile läheneme ...

Intuitsiooni järgi kasutame tavaliselt lineaarset otsingut, eks? Kuid nüüd teame, et binaarne otsing võib olla nii tõhus, eriti suure probleemi korral ...

Kuidas siis arendajana siluda?

Lõpetuseks tahan tsiteerida Dan Abramovit:

Kasutage binaarset otsingut ja teaduslikku meetodit. Mitte sõna otseses mõttes koodis, vaid selles, kuidas sellele läheneda. Kas teil on viga kutsete A ja B vahel? Pange palk keskel. Kas see jääb A ja keskpunkti vahele? Pange keskele veel üks logi. Kas mingil sisendil on midagi valesti? Kõrvaldage pool sisendist. See töötab? Proovige teist poolt. Jne silumine võib tunduda väga meelevaldne, kuid mehaaniliselt tehes on see arusaadav. Vaadake, moodustage hüpotees, leidke viis seda testida, korrata. Ja lõika asjad pooleks, kui neid on liiga palju.

Viide: