Binary search: Difference between revisions
Content added Content deleted
(→{{header|Haskell}}: A variant which returns an Either value, and uses a helper function with a simpler type.) |
|||
| Line 2,045: | Line 2,045: | ||
<pre>'mu' found at index 9</pre> |
<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). |
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}}== |
=={{header|HicEst}}== |
||