module HaskellWorks.Data.Search
  ( binarySearch
  ) where

-- | Perform a binary search in the domain of function @f, bounded by the values @p and @q
-- to find the least value @v such that: @w <= (f v)
binarySearch :: (Ord a, Integral n) => a -> (n -> a) -> n -> n -> n
binarySearch :: a -> (n -> a) -> n -> n -> n
binarySearch a
w n -> a
f n
p n
q = if n
p n -> n -> n
forall a. Num a => a -> a -> a
+ n
1 n -> n -> Bool
forall a. Ord a => a -> a -> Bool
>= n
q
  then n
p
  else let m :: n
m = (n
p n -> n -> n
forall a. Num a => a -> a -> a
+ n
q) n -> n -> n
forall a. Integral a => a -> a -> a
`div` n
2 in
    if a
w a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= n -> a
f n
m
      then a -> (n -> a) -> n -> n -> n
forall a n. (Ord a, Integral n) => a -> (n -> a) -> n -> n -> n
binarySearch a
w n -> a
f n
p n
m
      else a -> (n -> a) -> n -> n -> n
forall a n. (Ord a, Integral n) => a -> (n -> a) -> n -> n -> n
binarySearch a
w n -> a
f n
m n
q
{-# INLINE binarySearch #-}