- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
import Data.Array
import Control.Arrow
l = [1,5,5,5,8,10,17]
make_array [] = undefined
make_array l = listArray (0, (length l)-1) l
-- binary_search:: (Integral i, Num i, Ord e, Ix i) => e -> Array i e -> i
binary_search item arr = bs la ra where
(la, ra) = bounds arr
nextWhileEqualItem = uncurry iterate >>> takeWhile (\i -> la<=i && i<=ra && arr!i==item) >>> last
bs l r
| (m == l || m == r) && item/=av = Nothing
| item<av = bs l m
| item>av = bs m r
| item==av = Just (nextWhileEqualItem ((+) (-1), m), nextWhileEqualItem ((+)1, m))
| otherwise = Nothing
where
m = (l+r) `div` 2
av = arr!m
main = do
print $ binary_search 8 $ make_array l
print $ binary_search 5 $ make_array l
print $ binary_search 5 $ make_array $ tail l
print $ binary_search 0 $ make_array l
print $ binary_search 100 $ make_array l
print $ binary_search 9 $ make_array l
Решил я значит поучаствовать в специальной олимпиаде Романа с двача.
http://ideone.com/K5Jj59