AtCoder.Extra.Bisect

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, right point of the boundary

Example

Perform index compression:

>>> import AtCoder.Extra.Bisect
>>> import Data.Maybe (fromJust)
>>> 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 (fromJust . lowerBound dict) xs
[0,2,1,4,3]

Since: 1.1.0.0

C++-like binary search

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

\(O(\log n)\) Returns the index of the first element \(x\) in the vector such that \(x \ge x_0\), or Nothing if no such element exists.

Y Y Y Y Y N N N N N      Y: (< x0)
--------- *---------> X  N: (>= x0)
          R              R: returning point

Example

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

>>> lowerBound xs 2
Just 2

>>> lowerBound xs 3
Just 4

>>> lowerBound xs 4
Just 4

Out of range values:

>>> lowerBound xs 0
Just 0

>>> lowerBound xs 5
Nothing

Since: 1.1.0.0

lowerBoundIn :: (Vector v a, Ord a) => Int -> Int -> v a -> a -> Maybe Int

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

• The user predicate evaluates indices in \([l, r)\).
• The interval \([l, r)\) is silently clamped to ensure it remains within the bounds \([0, n)\).

Example

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

>>> lowerBoundIn 2 5 xs 20
Just 2

>>> lowerBoundIn 2 5 xs 30
Just 4

>>> lowerBoundIn 2 5 xs 40
Just 4

>>> lowerBoundIn 2 5 xs 50
Nothing

Since: 1.1.0.0

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

\(O(\log n)\) Returns the index of the first element \(x\) in the vector such that \(x \gt x_0\), or Nothing if no such element exists.

Y Y Y Y Y N N N N N      Y: (<= x0)
--------- *---------> X  N: (> x0)
          R              R: returning point

Example

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

>>> upperBound xs 20
Just 4

>>> upperBound xs 30
Just 4

>>> upperBound xs 40
Nothing

Out of range values:

>>> upperBound xs 0
Just 0

>>> upperBound xs 50
Nothing

Since: 1.1.0.0

upperBoundIn :: (Vector v a, Ord a) => Int -> Int -> v a -> a -> Maybe Int

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

• The user predicate evaluates indices in \([l, r)\).
• The interval \([l, r)\) is silently clamped to ensure it remains within the bounds \([0, n)\).

Example

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

>>> upperBoundIn 2 5 xs 10
Just 2

>>> upperBoundIn 2 5 xs 20
Just 4

>>> upperBoundIn 2 5 xs 30
Just 4

>>> upperBoundIn 2 5 xs 40
Nothing

>>> upperBoundIn 2 5 xs 50
Nothing

Since: 1.1.0.0

Generic bisection method

bisectL :: HasCallStack => Int -> Int -> (Int -> Bool) -> Maybe Int

\(O(\log n)\) Applies the bisection method on a half-open interval \([l, r)\) and returns the left boundary point, or Nothing if no such point exists.

Y Y Y Y Y N N N N N      Y: user predicate holds
--------* ----------> X  N: user predicate does not hold
        L                L: the left boundary point returned

Example

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

>>> bisectL 0 n ((<= 0) . (xs VU.!))
Nothing

>>> bisectL 0 n ((<= 100) . (xs VU.!))
Just 5

>>> bisectL 0 3 ((<= 20) . (xs VU.!))
Just 2

Since: 1.1.0.0

bisectLM :: (HasCallStack, Monad m) => Int -> Int -> (Int -> m Bool) -> m (Maybe Int)

\(O(\log n)\) Monadic variant of bisectL.

Since: 1.1.0.0

bisectR :: HasCallStack => Int -> Int -> (Int -> Bool) -> Maybe Int

\(O(\log n)\) Applies the bisection method on a half-open interval \([l, r)\) and returns the right boundary point, or Nothing if no such point exists.

Y Y Y Y Y N N N N N      Y: user predicate holds
--------- *---------> X  N: user predicate does not hold
          R              R: the right boundary point returned

Example

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

>>> bisectR 0 n ((<= 0) . (xs VU.!))
Just 0

>>> bisectR 0 n ((<= 100) . (xs VU.!))
Nothing

>>> bisectR 0 4 ((<= 20) . (xs VU.!))
Nothing

Since: 1.1.0.0

bisectRM :: (HasCallStack, Monad m) => Int -> Int -> (Int -> m Bool) -> m (Maybe Int)

\(O(\log n)\) Monadic variant of bisectR.

Since: 1.1.0.0