Skip to content

Instantly share code, notes, and snippets.

@luochen1990
Last active October 14, 2020 09:03
Show Gist options
  • Save luochen1990/1cdbe6a4aa6404355a69 to your computer and use it in GitHub Desktop.
Save luochen1990/1cdbe6a4aa6404355a69 to your computer and use it in GitHub Desktop.
Binary Search in Haskell
module BinarySearch(binarySearch, discreteBinarySearch, continuousBinarySearch) where
binarySearch :: ((a -> a -> Bool), (a -> a -> a)) -> (a, a) -> (a -> Bool) -> Maybe a
binarySearch (closeEnough, mid) (x0, x1) f = if y0 == y1 then Nothing else Just (iter x0 x1 y0 y1) where
(y0, y1) = (f x0, f x1)
iter x0 x1 y0 y1 = if closeEnough x0 x1
then (if y0 then x0 else x1)
else
let
xm = mid x0 x1
ym = f xm
in
if ym /= y0
then iter x0 xm y0 ym
else iter xm x1 ym y1
discreteBinarySearch :: (Integral a) => (a, a) -> (a -> Bool) -> Maybe a
discreteBinarySearch = binarySearch ((\a -> \b -> abs(a - b) <= 1), (\a -> \b -> (a + b) `div` 2))
continuousBinarySearch :: (Floating a, Ord a) => a -> (a, a) -> (a -> Bool) -> Maybe a
continuousBinarySearch eps = binarySearch ((\a -> \b -> abs(a - b) <= eps), (\a -> \b -> (a + b) / 2))
main = do
print $ continuousBinarySearch 1e-6 (0, 1e6) ((>=2) . (**2))
print $ discreteBinarySearch (0, 10000) ((>=25) . (^2))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment