Binary search: Difference between revisions
→{{header|Haskell}}: Added an encoding of the iterative algorithm in terms of 'until'
(→{{header|Haskell}}: Corrected inner lines of helper function) |
(→{{header|Haskell}}: Added an encoding of the iterative algorithm in terms of 'until') |
||
Line 1,989:
=={{header|Haskell}}==
===Recursive algorithm===
The algorithm itself, parametrized by an "interrogation" predicate ''p'' in the spirit of the explanation above:
<lang haskell>import Data.Array (Array, Ix, (!), listArray, bounds)
Line 2,102 ⟶ 2,104:
Left x -> "\' " ++ x
Right x -> "' found at index " ++ show x</lang>
===Iterative algorithm===
The iterative algorithm could be written in terms of the '''until''' function, which takes a predicate '''p''', a function '''f''', and a seed value '''x'''.
It returns the result of applying f until p holds.
<lang haskell>import Data.Array (Array, Ix, (!), listArray, bounds)
-- ITERATIVE SEARCH IN TERMS OF 'UNTIL' -------------------
bIterSearchArray
:: (Ix i, Integral i, Ord e)
=> Array i e -> e -> Either String i
bIterSearchArray a x = findIter (compare x . (a !)) (bounds a)
findIter
:: Integral a
=> (a -> Ordering) -> (a, a) -> Either String a
findIter p (low, high) =
let (lo, hi) =
until
(\(lo, hi) -> lo > hi || 0 == hi)
(\(lo, hi) ->
let m = quot (lo + hi) 2
in case p m of
LT -> (lo, pred m)
GT -> (succ m, hi)
EQ -> (m, 0))
(low, high)
in if 0 /= hi
then Left "not found"
else Right lo
-- TEST ---------------------------------------------------
haystack
:: (Num i, Ix i)
=> Array i String
haystack =
listArray
(0, 11)
[ "alpha"
, "beta"
, "delta"
, "epsilon"
, "eta"
, "gamma"
, "iota"
, "kappa"
, "lambda"
, "mu"
, "theta"
, "zeta"
]
main :: IO ()
main =
let needle = "mu"
lrFound = bIterSearchArray haystack needle
in putStrLn $
'\'' :
needle ++
case lrFound of
Left x -> "\' " ++ x
Right x -> "' found at index " ++ show x</lang>
{{Out}}
<pre>'mu' found at index 9</pre>
=={{header|HicEst}}==
| |||