Trait BinarySearch

pub trait BinarySearch<T> {
    // Required methods
    fn lower_bound(&self, value: &T) -> usize;
    fn upper_bound(&self, value: &T) -> usize;

    // Provided method
    fn equal_range(&self, value: &T) -> (usize, usize) { ... }
}

BinarySearch::lower_bound,BinarySearch::upper_boundを提供する。

Required Methods

fn lower_bound(&self, value: &T) -> usize

x以上となる最小のindexを求める。

fn upper_bound(&self, value: &T) -> usize

xを超える最小のindexを求める。

Provided Methods

fn equal_range(&self, value: &T) -> (usize, usize)

lower_bound, upper_boundの組を求める。

Implementations on Foreign Types

impl<T: Ord> BinarySearch<T> for [T]

fn lower_bound(&self, value: &T) -> usize

x以上となる最小のindexを求める。

Time complexity $O(\log n)$

fn upper_bound(&self, value: &T) -> usize

xを超える最小のindexを求める。

Time complexity $O(\log n)$

Implementors