Posted By

rtperson on 11/30/12


Tagged


Versions (?)

Binary Search in Haskell


 / Published in: Haskell
 

Improved version, using lenses instead of the dangerous (!!) operator for list access.

  1. module BinarySearch where
  2.  
  3. import Control.Lens
  4. import Data.Maybe
  5.  
  6. a :: [Int]
  7. a = [6, 13, 14, 25, 33, 43, 51, 53, 64, 72, 84, 93, 95, 96, 97]
  8.  
  9. bsearch :: Int -> [Int] -> Maybe Int
  10. bsearch _ [] = Nothing
  11. bsearch key xs
  12. | key < fromJust val = bsearch key (take (mid-1) xs)
  13. | key > fromJust val = bsearch key (drop (mid+1) xs)
  14. | otherwise = val
  15. where
  16. mid = floor ((fromIntegral $ (length xs) - 1) / 2)
  17. val = xs ^? ix mid

Report this snippet  

You need to login to post a comment.