Trait nekolib::traits::bisect::Bisect

source ·
pub trait Bisect {
    type Input;
    type Output;

    // Required method
    fn bisect(&self, pred: impl FnMut(&Self::Input) -> bool) -> Self::Output;
}
Expand description

二分探索。

$\gdef\halfopen#1#2{[#1, #2)}$ 述語 $f$ は、ある $x$ に対して次が成り立つとする。

  • $y\in\halfopen{L}{x} \implies f(y)$
  • $y\in\halfopen{x}{R} \implies \lnot f(y)$

この $x$ を返す。

Idea

Notes

下端が条件を満たすかを判定するのが不都合なときは、下端を一つ大きく取って別で処理するとよいかも。 cf. 提出 #34955711

Examples

use nekolib::traits::Bisect;

let pred = |&x: &i32| x * x < 200;
assert_eq!((0..100).bisect(pred), 15);
assert_eq!((0..).bisect(pred), 15);

let a = [0, 1, 4, 5, 5, 5, 9];
let pred = |&x: &i32| x < 5;
assert_eq!(a.bisect(pred), 3);
assert_eq!(a[5..].bisect(pred), 0); // [5, 9]
assert_eq!(a[..0].bisect(pred), 0); // []

let pred = |&x: &f64| 2.0_f64.powf(x) < 3.0;
let lg3 = 3.0_f64.log2();
// 1.584962500721156
assert!(((1.0_f64..2.0).bisect(pred) - lg3).abs() <= 1e-16);
assert_eq!((1.0_f64..2.0).bisect(pred), lg3); // !

Required Associated Types§

Required Methods§

source

fn bisect(&self, pred: impl FnMut(&Self::Input) -> bool) -> Self::Output

Implementations on Foreign Types§

source§

impl Bisect for RangeTo<i32>

§

type Input = i32

§

type Output = i32

source§

fn bisect(&self, pred: impl FnMut(&i32) -> bool) -> i32

source§

impl Bisect for RangeTo<isize>

§

type Input = isize

§

type Output = isize

source§

fn bisect(&self, pred: impl FnMut(&isize) -> bool) -> isize

source§

impl Bisect for Range<i128>

§

type Input = i128

§

type Output = i128

source§

fn bisect(&self, pred: impl FnMut(&i128) -> bool) -> i128

source§

impl Bisect for RangeTo<i128>

§

type Input = i128

§

type Output = i128

source§

fn bisect(&self, pred: impl FnMut(&i128) -> bool) -> i128

source§

impl Bisect for RangeTo<usize>

§

type Input = usize

§

type Output = usize

source§

fn bisect(&self, pred: impl FnMut(&usize) -> bool) -> usize

source§

impl Bisect for RangeTo<u128>

§

type Input = u128

§

type Output = u128

source§

fn bisect(&self, pred: impl FnMut(&u128) -> bool) -> u128

source§

impl Bisect for RangeFrom<i16>

§

type Input = i16

§

type Output = i16

source§

fn bisect(&self, pred: impl FnMut(&i16) -> bool) -> i16

source§

impl Bisect for Range<u8>

§

type Input = u8

§

type Output = u8

source§

fn bisect(&self, pred: impl FnMut(&u8) -> bool) -> u8

source§

impl Bisect for Range<f32>

§

type Input = f32

§

type Output = f32

source§

fn bisect(&self, pred: impl FnMut(&f32) -> bool) -> f32

source§

impl Bisect for RangeTo<i64>

§

type Input = i64

§

type Output = i64

source§

fn bisect(&self, pred: impl FnMut(&i64) -> bool) -> i64

source§

impl Bisect for RangeFrom<i32>

§

type Input = i32

§

type Output = i32

source§

fn bisect(&self, pred: impl FnMut(&i32) -> bool) -> i32

source§

impl Bisect for Range<u32>

§

type Input = u32

§

type Output = u32

source§

fn bisect(&self, pred: impl FnMut(&u32) -> bool) -> u32

source§

impl Bisect for Range<u128>

§

type Input = u128

§

type Output = u128

source§

fn bisect(&self, pred: impl FnMut(&u128) -> bool) -> u128

source§

impl Bisect for Range<i32>

§

type Input = i32

§

type Output = i32

source§

fn bisect(&self, pred: impl FnMut(&i32) -> bool) -> i32

source§

impl Bisect for RangeFrom<u32>

§

type Input = u32

§

type Output = u32

source§

fn bisect(&self, pred: impl FnMut(&u32) -> bool) -> u32

source§

impl Bisect for Range<i16>

§

type Input = i16

§

type Output = i16

source§

fn bisect(&self, pred: impl FnMut(&i16) -> bool) -> i16

source§

impl Bisect for Range<i8>

§

type Input = i8

§

type Output = i8

source§

fn bisect(&self, pred: impl FnMut(&i8) -> bool) -> i8

source§

impl Bisect for RangeFrom<u128>

§

type Input = u128

§

type Output = u128

source§

fn bisect(&self, pred: impl FnMut(&u128) -> bool) -> u128

source§

impl Bisect for RangeFrom<u8>

§

type Input = u8

§

type Output = u8

source§

fn bisect(&self, pred: impl FnMut(&u8) -> bool) -> u8

source§

impl<T> Bisect for [T]

§

type Input = T

§

type Output = usize

source§

fn bisect(&self, pred: impl FnMut(&T) -> bool) -> usize

source§

impl Bisect for RangeTo<u64>

§

type Input = u64

§

type Output = u64

source§

fn bisect(&self, pred: impl FnMut(&u64) -> bool) -> u64

source§

impl Bisect for RangeFrom<isize>

§

type Input = isize

§

type Output = isize

source§

fn bisect(&self, pred: impl FnMut(&isize) -> bool) -> isize

source§

impl Bisect for RangeFrom<u64>

§

type Input = u64

§

type Output = u64

source§

fn bisect(&self, pred: impl FnMut(&u64) -> bool) -> u64

source§

impl Bisect for RangeTo<u32>

§

type Input = u32

§

type Output = u32

source§

fn bisect(&self, pred: impl FnMut(&u32) -> bool) -> u32

source§

impl Bisect for RangeFrom<i8>

§

type Input = i8

§

type Output = i8

source§

fn bisect(&self, pred: impl FnMut(&i8) -> bool) -> i8

source§

impl Bisect for Range<i64>

§

type Input = i64

§

type Output = i64

source§

fn bisect(&self, pred: impl FnMut(&i64) -> bool) -> i64

source§

impl Bisect for RangeFrom<u16>

§

type Input = u16

§

type Output = u16

source§

fn bisect(&self, pred: impl FnMut(&u16) -> bool) -> u16

source§

impl Bisect for RangeTo<u16>

§

type Input = u16

§

type Output = u16

source§

fn bisect(&self, pred: impl FnMut(&u16) -> bool) -> u16

source§

impl Bisect for RangeFrom<usize>

§

type Input = usize

§

type Output = usize

source§

fn bisect(&self, pred: impl FnMut(&usize) -> bool) -> usize

source§

impl Bisect for Range<usize>

§

type Input = usize

§

type Output = usize

source§

fn bisect(&self, pred: impl FnMut(&usize) -> bool) -> usize

source§

impl Bisect for Range<isize>

§

type Input = isize

§

type Output = isize

source§

fn bisect(&self, pred: impl FnMut(&isize) -> bool) -> isize

source§

impl Bisect for RangeTo<u8>

§

type Input = u8

§

type Output = u8

source§

fn bisect(&self, pred: impl FnMut(&u8) -> bool) -> u8

source§

impl Bisect for Range<f64>

§

type Input = f64

§

type Output = f64

source§

fn bisect(&self, pred: impl FnMut(&f64) -> bool) -> f64

source§

impl Bisect for Range<u64>

§

type Input = u64

§

type Output = u64

source§

fn bisect(&self, pred: impl FnMut(&u64) -> bool) -> u64

source§

impl Bisect for RangeFrom<i64>

§

type Input = i64

§

type Output = i64

source§

fn bisect(&self, pred: impl FnMut(&i64) -> bool) -> i64

source§

impl Bisect for RangeFrom<i128>

§

type Input = i128

§

type Output = i128

source§

fn bisect(&self, pred: impl FnMut(&i128) -> bool) -> i128

source§

impl Bisect for Range<u16>

§

type Input = u16

§

type Output = u16

source§

fn bisect(&self, pred: impl FnMut(&u16) -> bool) -> u16

source§

impl Bisect for RangeTo<i16>

§

type Input = i16

§

type Output = i16

source§

fn bisect(&self, pred: impl FnMut(&i16) -> bool) -> i16

source§

impl Bisect for RangeTo<i8>

§

type Input = i8

§

type Output = i8

source§

fn bisect(&self, pred: impl FnMut(&i8) -> bool) -> i8

Implementors§