Binary search: Difference between revisions
→{{header|Haskell}}: A variant which returns an Either value, and uses a helper function with a simpler type.
(→{{header|Haskell}}: A variant which returns an Either value, and uses a helper function with a simpler type.) |
|||
Line 2,045:
<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).
A common optimisation of recursion is to delegate the main computation to a helper function with simpler type signature. For the option type of the return value, we could also use an Either as an alternative to a Maybe.
<lang haskell>import Data.Array (Array, Ix, (!), listArray, bounds)
-- BINARY SEARCH USING A HELPER FUNCTION WITH A SIMPLER TYPE SIGNATURE
bSearch
:: Integral a
=> (a -> Ordering) -> (a, a) -> Either String a
bSearch p (low, high) =
let go lo hi
| hi < lo = Left "not found"
| otherwise =
let mid = (lo + hi) `div` 2
in case p mid of
LT -> bSearch p (lo, mid - 1)
GT -> bSearch p (mid + 1, hi)
EQ -> Right mid
in go low high
-- Application to an array:
bSearchArray
:: (Ix i, Integral i, Ord e)
=> Array i e -> e -> Either String i
bSearchArray a x = bSearch (compare x . (a !)) (bounds a)</lang>
=={{header|HicEst}}==
| |||