| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Algorithm.Bisect
Description
\(O(\log N)\) bisection method for sorted items in an inclusive range (from left to right only).
Synopsis
- bisectImpl :: (Eq i, Monad m) => (i -> i -> Maybe i) -> i -> i -> i -> i -> (i -> m Bool) -> m (Maybe i, Maybe i)
- getMidDouble :: Double -> Double -> Double -> Maybe Double
- bisectMF64 :: Monad m => Double -> Double -> Double -> (Double -> m Bool) -> m (Maybe Double, Maybe Double)
- bisectMLF64 :: Monad m => Double -> Double -> Double -> (Double -> m Bool) -> m (Maybe Double)
- bisectMRF64 :: Monad m => Double -> Double -> Double -> (Double -> m Bool) -> m (Maybe Double)
- bisectF64 :: Double -> Double -> Double -> (Double -> Bool) -> (Maybe Double, Maybe Double)
- bisectLF64 :: Double -> Double -> Double -> (Double -> Bool) -> Maybe Double
- bisectRF64 :: Double -> Double -> Double -> (Double -> Bool) -> Maybe Double
Common bisection method implementation
bisectImpl :: (Eq i, Monad m) => (i -> i -> Maybe i) -> i -> i -> i -> i -> (i -> m Bool) -> m (Maybe i, Maybe i) #
\(O(f \log N)\) Bisection method implementation. It's generalized over both the index type and the monad.
Parameters
getMid: Returns the mid index between two. ReturnsNothingif the two indices are close enough.lowOut: Nearest low index that is NOT included in the range.highOut: Nearest high index that is NOT included in the range.
getMidDouble :: Double -> Double -> Double -> Maybe Double #
getMid parameter of bisectImpl for Double indices.
Bisection method for Double range
bisectMF64 :: Monad m => Double -> Double -> Double -> (Double -> m Bool) -> m (Maybe Double, Maybe Double) #
\(O(f \log N)\) Monadic binary search for an Double range.
bisectMLF64 :: Monad m => Double -> Double -> Double -> (Double -> m Bool) -> m (Maybe Double) #
\(O(f \log N)\)
bisectMRF64 :: Monad m => Double -> Double -> Double -> (Double -> m Bool) -> m (Maybe Double) #
\(O(f \log N)\)
bisectF64 :: Double -> Double -> Double -> (Double -> Bool) -> (Maybe Double, Maybe Double) #
\(O(f \log N)\) Pure binary search for an Double range.