Invariantas

Pirmoje pamokoje tiesinė paieška 100 000 įrašų bibliotekoje kainavo 100 000 palyginimų. Dvejetainė kainuos 17.

Sąlyga viena: biblioteka turi būti surikiuota. Tai pirmas kartas kurse, kai tvarka yra ne malonumas, o būtinybė — ir tai klausimas, į kurį atsakys 7–9 pamokos.

Invariantas

Paieška laiko du kraštus, lo ir hi, ir viena taisyklė galioja visą laiką:

atsakymas visada yra tarp lo ir hi.

Pradžioje lo = 0, o hi = len(items) — viena vieta už galo. Tai ne klaida: „nerasta" yra teisėtas atsakymas, ir jis gyvena būtent ten.

Kiekviename žingsnyje imamas vidurys ir pusė intervalo atmetama:

  jei items[mid] < target:  lo = mid + 1   // mid per mažas, atsakymu būti negali
  kitaip:                   hi = mid       // mid GALI būti atsakymas, lieka

Asimetrija tarp mid + 1 ir mid yra visa esmė. Kas pirmą kartą rašo dvejetainę paiešką, dažniausiai suklysta būtent čia — ir gauna amžinąjį ciklą arba atsakymą, prašovusį per vieną.

Ką grąžinam

Ne „ar radau", o pirmo įrašo, kuris ≥ ieškomo, indeksą. Tai vadinama at-or-after, ir taip elgiasi transit: „koks artimiausias autobusas nuo 8:00".

Tikslaus atitikmens paieška yra šitas plius vienas patikrinimas. Atvirkščiai nebūna: iš „radau/neradau" atsakymo nebeišspausi, kur įrašas būtų buvęs.

Spėk prieš skaitydamas toliau

17 palyginimų prieš 100 000. Atrodo, kad ginčytis nėra dėl ko.

Nuo kokio n dvejetainė paieška pradeda laimėti pagal LAIKRODĮ?

Užsirašyk skaičių. Ir dar vieną: ar tas skaičius vienas?