{-|

Module      : BinarySearch
Description : Example binary search
Copyright   : © Frank Jung, 2020
License     : GPL-3

Example implementation of
<https://en.wikipedia.org/wiki/Binary_search_algorithm binary search>.

-}

module BinarySearch (bsearch) where

-- import           Control.Lens (ix, (^?))
import           Data.Maybe (fromJust, listToMaybe)

-- | Binary Search
--
-- Example using an integer array, search list @[1..6]@ for values @[1..8]@.
--
-- Expect @1..6@ will return 'Just' values, while @7@ and @8@ will return
-- 'Nothing'.
--
-- The same also applies for strings. Try "abcdef" and "gh".
bsearch :: (Ord a) => [a] -> a -> Maybe a
bsearch :: forall a. Ord a => [a] -> a -> Maybe a
bsearch [] a
_ = Maybe a
forall a. Maybe a
Nothing
bsearch [a]
xs a
key
    | a
key a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< Maybe a -> a
forall a. HasCallStack => Maybe a -> a
fromJust Maybe a
val = [a] -> a -> Maybe a
forall a. Ord a => [a] -> a -> Maybe a
bsearch (Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
take Int
mid [a]
xs) a
key
    | a
key a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> Maybe a -> a
forall a. HasCallStack => Maybe a -> a
fromJust Maybe a
val = [a] -> a -> Maybe a
forall a. Ord a => [a] -> a -> Maybe a
bsearch (Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
drop (Int
mid Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) [a]
xs) a
key
    | Bool
otherwise = Maybe a
val
  where
    mid :: Int
mid = [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2
    val :: Maybe a
val = [a] -> Maybe a
forall a. [a] -> Maybe a
listToMaybe (Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
drop Int
mid [a]
xs)
    -- val = xs ^? ix mid     -- from Control.Lens