Ҷустуҷӯи бинарӣ аз рӯи ҷавоб

Ҷустуҷӯи дуӣ аз рӯи ҷавоб

Идея

Баъзан мо на унсурро дар массив меҷӯем, балки хурдтарин ё калонтарин ҷавоберо, ки ба шарт ҷавобгӯ бошад.

Равиш чунин аст:

• ҷавоби эҳтимолиро mid месанҷем;
• месанҷем: мувофиқ аст ё не;
• агар мувофиқ бошад — кӯшиш мекунем ҷавобро беҳтар кунем;
• агар мувофиқ набошад — минбаъд меҷӯем.

Шарти асосӣ

Бояд монотонӣ иҷро шавад:

• агар mid мувофиқ бошад, пас ҳамаи калонтар (ё, дар гузориши дигар, ҳама хурдтар) қиматҳо низ мувофиқанд;
• агар mid мувофиқ набошад, пас ҳамаи хурдтар (ё калонтар) низ мувофиқ нестанд.

Маҳз ҳамин хосият имкон медиҳад, ки ҷустуҷӯи бинарӣ аз рӯи ҷавоб татбиқ карда шавад.

Шаблон

Мисоли масъала

Адади бутуни $n$ дода шудааст, талаб мешавад хурдтарин адади бутуни $x \geq n^2$-ро ёфтан.