Skip to main content

binary_search_answer

rust_algorithms::searching

Function binary_search_answer 

Source 
pub fn binary_search_answer<F: Fn(i64) -> bool>(
    lo: i64,
    hi: i64,
    pred: F,
) -> Option<i64>
Expand description

Javob ustidan binary search — olimpiada va real hayotdagi eng kuchli usul.

lo..=hi oralig’ida pred monoton (false false ... false true true ... true) bo’lsa, pred(x) == true bo’lgan eng kichik x ni qaytaradi. Agar hech biri true bo’lmasa — None.

Qachon kerak: “eng kichik sig’im”, “eng qisqa vaqt”, “minimal tezlik” tipidagi masalalarda. Massiv emas, javoblar oralig’i bo’ylab qidiramiz.

  • Time: O(log(hi-lo) × pred narxi), Space: O(1).

§Misol: √x ning butun qismi

use rust_algorithms::searching::binary_search_answer;

let x = 1_000_000i64;
// "s*s >= x" birinchi marta rost bo'ladigan s ni topamiz
let s = binary_search_answer(0, x, |s| s * s >= x).unwrap();
assert_eq!(s, 1000);