[Haskell-beginners] Re: Code help requested

[Tim Perry]

Hi Joe,

I think you wanted (length list - 1) where you call do_search.  The version below is my rewrite with guards, this change, and "midVal" which keeps "list !! mid" from being evaluated twice per recursion.  Unfortunately, I have no idea how to work a fold into this.  Good luck!

--Tim


binary_find :: Ord a => [a] -> a -> Maybe Int
binary_find [] elem  = Nothing

binary_find list elem =
  do_search list elem 0 (length list -1)
  where
    do_search list elem low high
      | high < low = Nothing
      | midVal > elem = do_search list elem low (mid - 1)
      | midVal < elem = do_search list elem (mid + 1) high
      | otherwise = Just mid
      where
        midVal = list !! mid
        mid = low + (high - low) `div` 2

main = do
  print $ binary_find [1] 2
  print $ binary_find [1,3] 1
  print $ binary_find [1,3,4] 3
  print $ binary_find [1,3,4] 4
  print $ binary_find [1,2,4,6,8,9,12,15,17,20] 17
  print $ binary_find "hello" 'l'
  print $ binary_find [0.0, 1.5, 3.0] 3.0

  print $ binary_find [] 1
  print $ binary_find [1,3] 2
  print $ binary_find [1,4,6,8,9,12,15,17,20] 2

  -- boom?
  print $ binary_find [1,4,6,8,9,12,15,17,20] 19