hgeometry-combinatorial-0.12.0.1: Data structures, and Data types.
Copyright(C) Frank Staals
Licensesee the LICENSE file
MaintainerFrank Staals
Safe HaskellNone
LanguageHaskell2010

Algorithms.BinarySearch

Description

 
Synopsis

Documentation

binarySearch :: Integral a => (a -> Bool) -> a -> a -> a Source #

Given a monotonic predicate p, a lower bound l, and an upper bound u, with: p l = False p u = True l < u.

Get the index h such that everything strictly smaller than h has: p i = False, and all i >= h, we have p h = True

running time: \(O(\log(u - l))\)

binarySearchUntil :: (Fractional r, Ord r) => r -> (r -> Bool) -> r -> r -> r Source #

Given a value \(\varepsilon\), a monotone predicate \(p\), and two values \(l\) and \(u\) with:

  • \(p l\) = False
  • \(p u\) = True
  • \(l < u\)

we find a value \(h\) such that:

  • \(p h\) = True
  • \(p (h - \varepsilon)\) = False
>>> binarySearchUntil (0.1) (>= 0.5) 0 (1 :: Double)
0.5
>>> binarySearchUntil (0.1) (>= 0.51) 0 (1 :: Double)
0.5625
>>> binarySearchUntil (0.01) (>= 0.51) 0 (1 :: Double)
0.515625

Binary Searching in some data structure

class BinarySearch v where Source #

Associated Types

type Index v :: * Source #

type Elem v :: * Source #

Methods

binarySearchIn :: (Elem v -> Bool) -> v -> Maybe (Elem v) Source #

Given a monotonic predicate p and a data structure v, find the element v[h] such that that

for every index i < h we have p v[i] = False, and for every inedx i >= h we have p v[i] = True

returns Nothing if no element satisfies p

running time: \(O(T*\log n)\), where \(T\) is the time to execute the predicate.

binarySearchIdxIn :: (Elem v -> Bool) -> v -> Maybe (Index v) Source #

Given a monotonic predicate p and a data structure v, find the index h such that that

for every index i < h we have p v[i] = False, and for every inedx i >= h we have p v[i] = True

returns Nothing if no element satisfies p

running time: \(O(T*\log n)\), where \(T\) is the time to execute the predicate.

Instances

Instances details
Vector v a => BinarySearch (v a) Source # 
Instance details

Defined in Algorithms.BinarySearch

Associated Types

type Index (v a) Source #

type Elem (v a) Source #

Methods

binarySearchIn :: (Elem (v a) -> Bool) -> v a -> Maybe (Elem (v a)) Source #

binarySearchIdxIn :: (Elem (v a) -> Bool) -> v a -> Maybe (Index (v a)) Source #

BinarySearch (Seq a) Source # 
Instance details

Defined in Algorithms.BinarySearch

Associated Types

type Index (Seq a) Source #

type Elem (Seq a) Source #

Methods

binarySearchIn :: (Elem (Seq a) -> Bool) -> Seq a -> Maybe (Elem (Seq a)) Source #

binarySearchIdxIn :: (Elem (Seq a) -> Bool) -> Seq a -> Maybe (Index (Seq a)) Source #

BinarySearch (Set a) Source # 
Instance details

Defined in Algorithms.BinarySearch

Associated Types

type Index (Set a) Source #

type Elem (Set a) Source #

Methods

binarySearchIn :: (Elem (Set a) -> Bool) -> Set a -> Maybe (Elem (Set a)) Source #

binarySearchIdxIn :: (Elem (Set a) -> Bool) -> Set a -> Maybe (Index (Set a)) Source #

Searching on a Sequence