Binary search: Difference between revisions
→{{header|Haskell}}: Added a test, ran hlint, hindent
(→{{header|Haskell}}: Added a test, ran hlint, hindent) |
|||
Line 1,781:
=={{header|Haskell}}==
The algorithm itself, parametrized by an "interrogation" predicate ''p'' in the spirit of the explanation above:
<lang haskell>
binarySearch p (low,high) ▼
-- BINARY SEARCH --------------------------------------------------------------
bSearch
:: Integral a
=> (a -> Ordering) -> (a, a) -> Maybe a
| high < low = Nothing
| otherwise =
LT ->
GT ->
EQ -> Just mid
-- Application to an array:
bSearchArray
:: (Ix i, Integral i, Ord e)
=> Array i e -> e -> Maybe i
bSearchArray a x = bSearch (compare x . (a !)) (bounds a)
-- TEST -----------------------------------------------------------------------
axs
:: (Num i, Ix i)
=> Array i String
axs =
listArray
(0, 11)
[ "alpha"
, "beta"
, "delta"
, "epsilon"
, "eta"
, "gamma"
, "iota"
, "kappa"
, "lambda"
, "mu"
, "theta"
, "zeta"
]
main :: IO ()
main =
let e = "mu"
found = bSearchArray axs e
in putStrLn $
'\'' :
e ++
case found of
Nothing -> "' Not found"
Just x -> "' found at index " ++ show x</lang>
{{Out}}
<pre>'mu' found at index 9</pre>
The algorithm uses tail recursion, so the iterative and the recursive approach are identical in Haskell (the compiler will convert recursive calls into jumps).
| |||