Binary search: Difference between revisions
Content added Content deleted
(→{{header|Haskell}}: Corrected inner lines of helper function) |
(→{{header|Haskell}}: Added an encoding of the iterative algorithm in terms of 'until') |
||
Line 1,989: | Line 1,989: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
===Recursive algorithm=== |
|||
The algorithm itself, parametrized by an "interrogation" predicate ''p'' in the spirit of the explanation above: |
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) |
<lang haskell>import Data.Array (Array, Ix, (!), listArray, bounds) |
||
Line 2,102: | Line 2,104: | ||
Left x -> "\' " ++ x |
Left x -> "\' " ++ x |
||
Right x -> "' found at index " ++ show x</lang> |
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}}== |
=={{header|HicEst}}== |