Dvejetainė paieška ir jos invariantas
Surikiuotame masyve su tiesiogine prieiga palyginkite ieškomą reikšmę su viduriniu raktu ir atmeskite tą pusę, kurioje jos negali būti; kartokite, kol rasite atitinkantį raktą arba likęs intervalas bus tuščias.
Esminės žinios
Surikiuotame masyve su tiesiogine prieiga palyginkite ieškomą reikšmę su viduriniu raktu ir atmeskite tą pusę, kurioje jos negali būti; kartokite, kol rasite atitinkantį raktą arba likęs intervalas bus tuščias. Kiekviename žingsnyje intervale išsaugomi visi galimi atitikmenys, o jo dydis sumažinamas perpus.
Sąlygos ir taikymo ribos
- Raktams taikoma nuosekli pilnoji tvarka, o palyginimų sąnaudos yra aprėžtos.
- Blogiausiu atveju palyginimų skaičius yra O(log n); nuoseklioji prieiga ir kintamo ilgio raktų palyginimai keičia sąnaudų modelį.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaitos 3 transkripto puslapiai 4–5: paieška surikiuotame masyve, dalijimas pusiau ir logaritminis rėžis.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaityti visi glaustai suformuluoti teiginiai (241), hipotezės, pateiktos lygtys ir susitarimai bei visos kilmės semantinės sąsajos (596); peržiūrėta visa autoriaus sudaryta 241 įrašo tikslių šaltinių patikros matrica ir deklaruoti apribojimai. Siekiant aprėpti visą įrašų rinkinį, perskaityti 105 ankstesni faktiškai paveldėti matematikos ir informacijos įrašai. Toliau išvardyti tikslingai ir nepriklausomai peržiūrėti pirminių šaltinių skyriai; tuo NETEIGIAMA, kad kiekvieno cituojamo šaltinio visas tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atlikta informacinio turinio peržiūra, o ne žmogaus eksperto patvirtinimas atitinkamoje mokslo srityje, išsamus vadovėlio atkūrimas ar eksperimentinis pakartojimas. Peržiūros įrašas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-binary-search
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra