Binarinė paieška, taip pat žinoma kaip „ pusiau intervalų paieška“, yra kompiuterių moksle naudojamas algoritmas, norint rasti masyvo nustatytą reikšmę (raktą). Kad paieška būtų dvejetainė, masyvas turi būti rūšiuojamas didėjimo arba mažėjimo tvarka.

Kaip tai veikia?

Kaip matote diagramoje, kiekviename algoritmo etape atliekamas palyginimas, o procedūrų šakos nukreipiamos į vieną iš dviejų krypčių. Konkrečiai, pagrindinė vertė lyginama su vidutiniu masyvo elementu. Jei raktų reikšmė yra mažesnė arba didesnė už šį vidurinį elementą, algoritmas žino, kuri pusė masyvo tęsti paiešką, nes masyvas yra rūšiuojamas. Šis procesas kartojamas palaipsniui mažesniuose masyvo segmentuose, kol bus nustatyta vertė.

Kadangi kiekvienas algoritmo žingsnis padalija masyvo dydį per pusę, binarinė paieška bus sėkmingai baigta logaritminiu laiku. Tai reiškia, kad n elementų masyvo blogiausias atvejis yra garantuotas log (n) operacijose.

Dvejetainiai, programavimo terminai, paieška