Advanced Search

Binary Search in Haskell

/ Published in: Haskell
Save to your folder(s)
Improved version, using lenses instead of the dangerous (!!) operator for list access.

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  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


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.