Binäärihaku

Löytää arvon järjestetystä taulukosta katsomalla keskelle ja hylkäämällä puolikkaan, jossa arvo ei voi olla. Jokainen vertailu puolittaa jäljellä olevan.

paras Ω(1)
keskimääräinen Θ(log n)
huonoin O(log n)
tila O(1)

Mitä nämä tarkoittavat?

Järjestetty: nousevassa järjestyksessä. Binäärihaku vaatii tämän; järjestämättömällä datalla se antaa vääriä vastauksia.
Puolittaminen: jokainen vertailu hylkää puolet jäljellä olevasta, sen puolen, jossa kohde ei voi olla.
log₂ n: kuinka monta kertaa n voidaan puolittaa, kunnes jäljellä on 1. 64 arvolla se on 6, joten enintään 7 vertailua.

keskikohta (mid)
löytyi
hylätty
kohde

0 / 14 askelta

Jokainen keskikohta, jonka haku voisi valita; ajo on yksi polku alaspäin. Tasot: 5 = ⌈log₂(24 + 1)⌉, suurin tarvittava vertailujen määrä.

Nopeus 8 askelta/s

Välilyönti: toisto tai tauko. Nuolinäppäimet: askel. Home ja End: alkuun tai loppuun.

Kokeile tätä: Valitse kohde, jota ei ole taulukossa. Haku päättyy silti viimeistään ⌈log₂(n + 1)⌉ vertailun jälkeen, kun lo ohittaa hi:n.

Miten se toimii

Binäärihaku pitää kaksi merkkiä, lo ja hi, sen taulukon osan ympärillä, jossa kohde voi vielä olla. Se katsoo keskimmäistä arvoa: jos se on kohde, valmista; jos se on pienempi, kohde voi olla vain oikealla, joten lo siirtyy keskikohdan ohi; jos suurempi, hi siirtyy sen eteen. Jokainen askel puolittaa loput: 64 arvoa vaatii enintään 7 vertailua ja miljoona enintään 20. Kun lo ohittaa hi:n, mitään ei ole jäljellä: arvoa ei ole taulukossa.

Milloin se on hyvä valinta

Käytä binäärihakua aina, kun data on järjestetty ja mihin tahansa kohtaan voi hypätä: sana järjestetyssä listassa, versio julkaisuhistoriassa, git bisect, lisäyskohta järjestetyssä taulukossa. Järjestämättömällä datalla se antaa vääriä vastauksia, ja järjestäminen ensin kannattaa vain, jos haet monta kertaa.