Safe Haskell	None
Language	GHC2021

AtCoder.Extra.Bisect

Contents

C++-like binary searches
Generic bisection methods

Description

Bisection methods and binary search functions. They partition a half-open interval $[l, r)$ into two and return either the left or the right point of the boundary.

Y Y Y Y Y N N N N N      Y: user predicate holds,
--------* *---------> x  N: user predicate does not hold,
        L R              L, R: left and right points of the boundary

Example

Expand

Perform index compression with lowerBound:

>>> import AtCoder.Extra.Bisect
>>> import Data.Vector.Algorithms.Intro qualified as VAI
>>> import Data.Vector.Unboxed qualified as VU
>>> let xs = VU.fromList ([0, 20, 10, 40, 30] :: [Int])
>>> let dict = VU.uniq $ VU.modify VAI.sort xs
>>> VU.map (lowerBound dict) xs
[0,2,1,4,3]

Since: 1.3.0.0

Synopsis

lowerBound :: (HasCallStack, Vector v a, Ord a) => v a -> a -> Int
lowerBoundIn :: (HasCallStack, Vector v a, Ord a) => Int -> Int -> v a -> a -> Int
upperBound :: (HasCallStack, Vector v a, Ord a) => v a -> a -> Int
upperBoundIn :: (HasCallStack, Vector v a, Ord a) => Int -> Int -> v a -> a -> Int
maxRight :: HasCallStack => Int -> Int -> (Int -> Bool) -> Int
maxRightM :: (HasCallStack, Monad m) => Int -> Int -> (Int -> m Bool) -> m Int
minLeft :: HasCallStack => Int -> Int -> (Int -> Bool) -> Int
minLeftM :: (HasCallStack, Monad m) => Int -> Int -> (Int -> m Bool) -> m Int

C++-like binary searches

lowerBound :: (HasCallStack, Vector v a, Ord a) => v a -> a -> Int Source #

$O(\log n)$ Returns the maximum $r$ where $x_i \lt x_{ref}$ holds for $i \in [0, r)$ .

Y Y Y Y Y N N N N N      Y: x_i < x_ref
--------- *---------> x  N: not Y
          R              R: the right boundary point returned

Example

Expand

>>> import Data.Vector.Unboxed qualified as VU
>>> let xs = VU.fromList [1, 1, 2, 2, 4, 4]
>>> lowerBound xs 1
0

>>> lowerBound xs 2
2

>>> lowerBound xs 3
4

>>> lowerBound xs 4
4

>>> lowerBound xs 5
6

Since: 1.3.0.0

lowerBoundIn :: (HasCallStack, Vector v a, Ord a) => Int -> Int -> v a -> a -> Int Source #

$O(\log n)$ Computes the lowerBound for a slice of a vector within the interval $[l, r)$ .

Constraints

$0 \le l \le r \le n$

Example

Expand

>>> import Data.Vector.Unboxed qualified as VU
>>> let xs = VU.fromList [10, 10, 20, 20, 40, 40]
>>> --                            *---*---*
>>> lowerBoundIn 2 5 xs 10
2

>>> lowerBoundIn 2 5 xs 20
2

>>> lowerBoundIn 2 5 xs 30
4

>>> lowerBoundIn 2 5 xs 40
4

>>> lowerBoundIn 2 5 xs 50
5

Since: 1.3.0.0

upperBound :: (HasCallStack, Vector v a, Ord a) => v a -> a -> Int Source #

$O(\log n)$ Returns the maximum $r$ where $x_i \le x_{ref}$ holds for $i \in [0, r)$ .

Y Y Y Y Y N N N N N      Y: x_i <= x_ref
--------- *---------> x  N: not Y
          R              R: the right boundary point returned

Example

Expand

>>> import Data.Vector.Unboxed qualified as VU
>>> let xs = VU.fromList [10, 10, 20, 20, 40, 40]
>>> upperBound xs 0
0

>>> upperBound xs 10
2

>>> upperBound xs 20
4

>>> upperBound xs 30
4

>>> upperBound xs 39
4

>>> upperBound xs 40
6

Since: 1.3.0.0

upperBoundIn :: (HasCallStack, Vector v a, Ord a) => Int -> Int -> v a -> a -> Int Source #

$O(\log n)$ Computes the upperBound for a slice of a vector within the interval $[l, r)$ .

Constraints

$0 \le l \le r \le n$

Example

Expand

>>> import Data.Vector.Unboxed qualified as VU
>>> let xs = VU.fromList [10, 10, 20, 20, 40, 40]
>>> --                            *---*---*
>>> upperBoundIn 2 5 xs 0
2

>>> upperBoundIn 2 5 xs 10
2

>>> upperBoundIn 2 5 xs 20
4

>>> upperBoundIn 2 5 xs 30
4

>>> upperBoundIn 2 5 xs 40
5

>>> upperBoundIn 2 5 xs 50
5

Since: 1.3.0.0

Generic bisection methods

maxRight Source #

Arguments

:: HasCallStack
=> Int	$l$
-> Int	$r$
-> (Int -> Bool)	$p$
-> Int	Maximum $r' (r' \le r)$ where $p(i)$ holds for $i \in [l, r')$ .

$O(\log n)$ Applies the bisection method on a half-open interval $[l, r)$ and returns the right boundary point.

Y Y Y Y Y N N N N N      Y: p(i) returns true
--------- *---------> x  N: not Y
          R              R: the right boundary point returned

Example

Expand

>>> import Data.Vector.Unboxed qualified as VU
>>> let xs = VU.fromList [10, 10, 20, 20, 30, 30]
>>> let n = VU.length xs
>>> maxRight 0 n ((<= 20) . (xs VU.!))
4

>>> maxRight 0 n ((<= 0) . (xs VU.!))
0

>>> maxRight 0 n ((<= 100) . (xs VU.!))
6

>>> maxRight 0 3 ((<= 20) . (xs VU.!))
3

Since: 1.3.0.0

maxRightM :: (HasCallStack, Monad m) => Int -> Int -> (Int -> m Bool) -> m Int Source #

$O(\log n)$ Monadic variant of maxRight.

Since: 1.3.0.0

minLeft Source #

Arguments

:: HasCallStack
=> Int	$l$
-> Int	$r$
-> (Int -> Bool)	$p$
-> Int	Minimum $l' (l' \ge l)$ where $p(i)$ holds for $i \in [l', r)$

$O(\log n)$ Applies the bisection method on a half-open interval $[l, r)$ and returns the left boundary point.

N N N N N Y Y Y Y Y      Y: p(i) returns true
--------* ----------> x  N: not Y
        L                L: the left boundary point returned

Example

Expand

>>> import Data.Vector.Unboxed qualified as VU
>>> let xs = VU.fromList [10, 10, 20, 20, 30, 30]
>>> let n = VU.length xs
>>> minLeft 0 n ((>= 20) . (xs VU.!))
2

>>> minLeft 0 n ((>= 0) . (xs VU.!))
0

>>> minLeft 0 n ((>= 100) . (xs VU.!))
6

Since: 1.3.0.0

minLeftM :: (HasCallStack, Monad m) => Int -> Int -> (Int -> m Bool) -> m Int Source #

$O(\log n)$ Monadic variant of minLeft.

Since: 1.3.0.0

Key	Shortcut
s	Open this search box
esc	Close this search box
↓,ctrl + j	Move down in search results
↑,ctrl + k	Move up in search results
↵	Go to active search result