module HaskellWorks.Data.Search
( binarySearch
) where
binarySearch :: (Ord a, Integral n) => a -> (n -> a) -> n -> n -> n
binarySearch :: forall a n. (Ord a, Integral n) => a -> (n -> a) -> n -> n -> n
binarySearch a
w n -> a
f n
p n
q = if n
p forall a. Num a => a -> a -> a
+ n
1 forall a. Ord a => a -> a -> Bool
>= n
q
then n
p
else let m :: n
m = (n
p forall a. Num a => a -> a -> a
+ n
q) forall a. Integral a => a -> a -> a
`div` n
2 in
if a
w forall a. Ord a => a -> a -> Bool
<= n -> a
f n
m
then forall a n. (Ord a, Integral n) => a -> (n -> a) -> n -> n -> n
binarySearch a
w n -> a
f n
p n
m
else 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 #-}