competitive_library/other/
binary_search.rs

1pub struct BinarySearch<T> {
2    target: T,
3    min: i64,
4    max: i64,
5}
6impl<T> BinarySearch<T> {
7    pub fn new(target: T, min: i64, max: i64) -> Self {
8        Self { target, min, max }
9    }
10    /// f が true を帰す最小値を探す
11    pub fn search<F>(&self, f: F) -> i64
12    where
13        F: Fn(&T, i64) -> bool,
14    {
15        let mut left = self.min;
16        let mut right = self.max;
17
18        while right - left > 1 {
19            let mid = left + (right - left) / 2;
20
21            if f(&self.target, mid) {
22                left = mid;
23            } else {
24                right = mid
25            };
26        }
27        right
28    }
29}
30
31#[cfg(test)]
32mod tests {
33    use super::*;
34    #[test]
35    fn test_binary_search() {
36        let v = (0_i64..100).filter(|x| x % 2 == 0).collect::<Vec<_>>();
37        let bs = BinarySearch::new(&v, -1, v.len() as i64);
38        for &i in v.iter() {
39            let ans = bs.search(|x, j| x[j as usize] < i);
40            assert_eq!(v[ans as usize], i)
41        }
42    }
43}

competitive_library/other/binary_search.rs

competitive_library/other/
binary_search.rs