Binäärihaku

Binäärihaku ( tunnetaan myös bisektiomenetelmänä tai dikotomiana ) on klassinen algoritmi elementin löytämiseksi lajitetusta taulukosta (vektorista), joka käyttää taulukon jakamista puoliksi. Käytetään tietojenkäsittelytieteessä , laskennallisessa matematiikassa ja matemaattisessa ohjelmointissa .

Binäärihaun erikoistapaus on puolittamismenetelmä , jota käytetään tietyn jatkuvan funktion juurien etsimiseen tietyltä aikaväliltä.

Elementin etsiminen järjestetystä taulukosta

1. Tietorakenteen keskellä olevan elementin arvon määrittäminen. Saatua arvoa verrataan avaimeen.
2. Jos avain on pienempi kuin keskiarvo, haku suoritetaan elementtien ensimmäisellä puoliskolla, muuten - toisessa.
3. Haku rajoittuu siihen, että valitun puolikkaan keskielementin arvo määritetään uudelleen ja sitä verrataan avaimeen.
4. Prosessi jatkuu, kunnes joko avainarvon sisältävä elementti löytyy tai hakuväli on tyhjä.

Vaikka koodi on melko yksinkertainen, siinä on muutamia sudenkuoppia.

• Koodi (first + last) / 2on virheellinen, jos firstja lastsopii yksilöllisesti niiden tyyppiin, mutta first+last ei [1] . Jos näin suuret taulukot ovat teoriassa mahdollisia, on turvauduttava temppuihin:
  • Käytä koodia first + (last - first) / 2, joka ei varmasti johda ylivuotoon, kun käsittelet ei-negatiivisia kokonaislukuja ja ensimmäinen<viimeinen.
    • Jos firstja last ovat osoittimia tai iteraattoreita , tällainen koodi on ainoa oikea, koska se ei riko abstraktiota ("osoitin + osoitin" -toiminto on jo virheellinen). Toki algoritmin monimutkaisuuden säilyttämiseksi tarvitsemme nopeita operaatioita “osoitin+numero → osoitin”, “osoitin−osoitin → numero”.
  • Jos firstja last ovat allekirjoitettuja tyyppejä, suorita laskenta allekirjoittamattomassa tyypissä: ((unsigned)first + (unsigned)last) / 2. Javalla  toimii seuraava koodi: ( allekirjoitettu (first + last) >>> 1binäärilisäys on sama kuin allekirjoittamaton, Java takaa tämän toiminnan myös ylivuodossa ja koko kaava toimii allekirjoitetuilla numeroilla etumerkittöminä).
  • Kirjoita laskelma assemblerissä siirtolipun avulla . Jotain sellaista add eax, b; rcr eax, 1. Mutta ei ole suositeltavaa käyttää pitkiä tyyppejäfirst + (last - first) / 2 , se on nopeampi.
• Yksittäiset virheet ovat yleisiä binäärihauissa , ja jokainen tällainen virhe muuttuu silmukaksi , ohitukseksi tai rajojen ulkopuolelta. Siksi on tärkeää testata tällaisia ​​tapauksia: tyhjä taulukko ( n=0), yksi elementti ( n=1), puuttuvan arvon etsiminen (liian suuri, liian pieni ja jossain keskellä), ensimmäisen ja viimeisen elementin etsiminen.
• Joskus vaaditaan, että jos xketjussa on useita esiintymiä, ei löydy yhtäkään, vaan välttämättä ensimmäinen (vaihtoehtona: viimeinen; tai ei ollenkaan x, vaan sitä seuraava elementti). [2] Esimerkiksi C++- funktio etsii ensimmäisen yhtäläisestä ja löytää  x:ää seuraavan alkion. Jos ei löydy, molemmat palauta paikka, johon ne lisätään.std::lower_boundstd::upper_bound

Tiedemies Jon Bentley väittää, että 90 % opiskelijoista unohtaa ottaa huomioon kaikki näistä vaatimuksista kehittäessään binaarihakua. Ja jopa Jonin itsensä kirjoittamassa ja kirjasta kirjaan siirtymässä koodissa sisään hiipi virhe: koodi ei kestä ylivuotoa [1] .

Java-toteutusesimerkki