47 lines
1018 B
Haskell
47 lines
1018 B
Haskell
import Data.Array (Array, Ix, (!), listArray, bounds)
|
|
|
|
-- BINARY SEARCH USING A HELPER FUNCTION WITH A SIMPLER TYPE SIGNATURE
|
|
findIndexBinary
|
|
:: Ord a
|
|
=> (a -> Ordering) -> Array Int a -> Either String Int
|
|
findIndexBinary p axs =
|
|
let go (lo, hi)
|
|
| hi < lo = Left "not found"
|
|
| otherwise =
|
|
let mid = (lo + hi) `div` 2
|
|
in case p (axs ! mid) of
|
|
LT -> go (lo, pred mid)
|
|
GT -> go (succ mid, hi)
|
|
EQ -> Right mid
|
|
in go (bounds axs)
|
|
|
|
-- TEST ---------------------------------------------------
|
|
haystack :: Array Int String
|
|
haystack =
|
|
listArray
|
|
(0, 11)
|
|
[ "alpha"
|
|
, "beta"
|
|
, "delta"
|
|
, "epsilon"
|
|
, "eta"
|
|
, "gamma"
|
|
, "iota"
|
|
, "kappa"
|
|
, "lambda"
|
|
, "mu"
|
|
, "theta"
|
|
, "zeta"
|
|
]
|
|
|
|
main :: IO ()
|
|
main =
|
|
let needle = "lambda"
|
|
in putStrLn $
|
|
'\'' :
|
|
needle ++
|
|
either
|
|
("' " ++)
|
|
(("' found at index " ++) . show)
|
|
(findIndexBinary (compare needle) haystack)
|