Бинардык издөө
Массив боюнча жана жооп боюнча бинардык издөө: O(log n), инварианттар жана типтүү каталар.
Эгер маалыматтар иреттелген болсо (же шарт монотондуу болсо: «кайсы бир жерге чейин — жок, андан ары — ооба»), экиге бөлүп издесе болот: ар бир кадам варианттардын жарымын ыргытат. Миллиард элемент — болгону 30 кадам. Бул — бинардык издөө, O(log n).
Аны кылдат жазуу керек: «бирге жаңылуу» каталары жана түбөлүк циклдер — теманын визиттик картасы. Ишенимдүү шаблон — [l, r) жарым интервалы: шарт аткарылган биринчи индексти издейбиз.
x тин биринчи кездешүүсү. Киргизиңиз: 6 5, андан кийин иреттелген массив 1 3 5 5 7 9
STL ичинде бул даяр бар: std::lower_bound(a.begin(), a.end(), x) x тен кичине эмес биринчи элементке итератор кайтарат, upper_bound — так чоңго. Бирок издөөнү кол менен жаза билүүгө милдеттүүсүз — төмөндөгү башкы олимпиадалык ыкмадан улам.
ЖООП боюнча бинардык издөө. Көбүнчө жооптун өзү монотондуу: «t убакытка батууга болобу?» — эгер t га мүмкүн болсо, t+1ге да мүмкүн. Анда «болбойт» менен «болот» ортосундагы чек бинардык издөө менен табылат, ал эми сизге текшерүүнү гана жазуу калат. Мисал: бүтүн сандык квадрат тамыр — m² саны n ден ашпаган эң чоң m.
Жооп боюнча бинардык издөө менен бүтүн тамыр. Киргизиңиз: 1000000000000
Үч классикалык ката:
1. Түбөлүк цикл: эгер АКЫРКЫ жараганды издесеңиз (l = mid), ортону өйдө тегеректөө керек: (l + r + 1) / 2. Антпесе r - l = 1 болгондо цикл илинип калат.
2. Ортонун ашып кетүүсү: башка тилдерде l + (r - l) / 2 деп жазышат; C++ тилинде long long менен адатта коопсуз, бирок муну эстен чыгарбаңыз.
3. Туура эмес чектер: жооп баштапкы [l, r] ичинде жатууга милдеттүү — четки маанилерди текшериңиз.
Тапшырма: k станок бар, ар бири баракты t секундада басат, n барак керек. Алар эң аз канча убакытта бүтүрөт? «T убакытта канча барак үлгүрөбүз» текшерүүсү менен жооп боюнча бинардык издөө аркылуу чечиңиз.
Сабакты өттүм деп белгилеңиз — 2-деңгээл аяктады!