galloping_search.hs

import Debug.Trace
import Data.List

-- galloping search.
search :: (Int -> Bool) -> Int -> Int -> Int
search test lo hi | lo == hi = hi
                  | test lo  = lo
                  | otherwise = go True lo 1 where
    go accel i 0 = i + 1
    go accel i step
      | i + step >= hi || test (i + step) = go False i (step `div` 2)
      | otherwise = go accel (i + step) (if accel then 2 * step else step `div` 2)

-- showing what it does.
instrument :: Ord a => [a] -> a -> Int -> Bool
instrument xs target i = trace ("probing " ++ show i ++ " -> " ++ show result) result
  where result = target <= (xs !! i)

test :: Ord a => a -> [a] -> Int
test k xs = search (instrument xs k) 0 (length xs)