- 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
minusator41 14.03.2014 13:15 # −12
absolut 14.03.2014 15:21 # −1
guest 14.03.2014 18:02 # +3
gost 15.03.2014 17:58 # 0
inkanus-gray 16.03.2014 00:52 # +1
bormand 16.03.2014 07:37 # +3
Vasiliy 16.03.2014 22:27 # 0
inkanus-gray 16.03.2014 22:30 # 0
Vasiliy 17.03.2014 12:25 # 0
bormand 17.03.2014 12:27 # 0
gost 26.03.2014 08:45 # 0
KonardinoHuyardino 26.03.2014 17:01 # −2
Vasiliy 02.04.2014 14:23 # 0
laMer007 02.04.2014 23:16 # 0
1024-- 03.04.2014 02:40 # +1
LispGovno 14.03.2014 13:20 # −1
minusator41 14.03.2014 13:26 # −11
guest 14.03.2014 15:57 # −6
minusator41 14.03.2014 15:59 # −9
Yuuri 20.03.2014 18:10 # 0
Алсо, (+) (-1) — это subtract 1 или pred, (+) 1 — это (+ 1) или succ, а вместо нескольких сравнений двух значений подряд лучше сделать case a `compare` b of LT -> ...; GT -> ...; EQ -> ...
laMer007 02.04.2014 23:14 # 0