competitive::algorithm

Function binary_search

Source 
pub fn binary_search<T, F>(f: F, ok: T, err: T) -> T
where
    T: Bisect,
    F: FnMut(&T) -> bool,
Expand description

binary search for monotone segment

if ok < err then search [ok, err) where t(ok), t, t, …. t, t(ret), f, … f, f, f, err

if err < ok then search (err, ok] where err, f, f, f, … f, t(ret), … t, t, t(ok)

Examples found in repository?
crates/competitive/src/algorithm/chromatic_number.rs (line 31)
30    pub fn chromatic_number(&self) -> usize {
31        binary_search(|&k| self.k_colorable(k), self.n, 0)
32    }
More examples
Hide additional examples
crates/competitive/src/algorithm/binary_search.rs (line 103)
102    fn position_bisect(&self, mut f: impl FnMut(&T) -> bool) -> usize {
103        binary_search(|i| f(&self[*i as usize]), self.len() as i64, -1) as usize
104    }
105    fn rposition_bisect(&self, mut f: impl FnMut(&T) -> bool) -> usize {
106        binary_search(|i| f(&self[i - 1]), 0, self.len() + 1)
107    }
crates/library_checker/src/math/min_of_mod_of_linear.rs (lines 11-15)
6pub fn min_of_mod_of_linear(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, t, query: [(i64, u64, i64, i64)]);
10    for (n, m, a, b) in query.take(t) {
11        let x = binary_search(
12            |&x| floor_sum_range_freq(0, n, a, b, m, 0..x + 1) > 0,
13            m as i64 - 1,
14            -1,
15        );
16        writeln!(writer, "{}", x).ok();
17    }
18}
crates/competitive/src/string/suffix_array.rs (lines 56-73)
55    pub fn range(&self, t: &[T], next: impl Fn(&T) -> T) -> Range<usize> {
56        let l = binary_search(
57            |&i| {
58                let mut si = self.sa[i as usize];
59                let mut ti = 0;
60                while si < self.pat.len() && ti < t.len() {
61                    match self.pat[si].cmp(&t[ti]) {
62                        Ordering::Less => return false,
63                        Ordering::Greater => return true,
64                        Ordering::Equal => {}
65                    }
66                    si += 1;
67                    ti += 1;
68                }
69                !(si >= self.pat.len() && ti < t.len())
70            },
71            self.sa.len() as isize,
72            -1,
73        ) as usize;
74        let r = binary_search(
75            |&i| {
76                let mut si = self.sa[i as usize];
77                let mut ti = 0;
78                while si < self.pat.len() && ti < t.len() {
79                    match if ti + 1 == t.len() {
80                        self.pat[si].cmp(&next(&t[ti]))
81                    } else {
82                        self.pat[si].cmp(&t[ti])
83                    } {
84                        Ordering::Less => return false,
85                        Ordering::Greater => return true,
86                        Ordering::Equal => {}
87                    }
88                    si += 1;
89                    ti += 1;
90                }
91                !(si >= self.pat.len() && ti < t.len())
92            },
93            self.sa.len() as isize,
94            l as isize - 1,
95        ) as usize;
96        l..r
97    }