## Binary search in Haskell

Now a days i am addicted to Haskell programming and try to learn as much as possible. The best thing to learn a programming language is writing codes. I tried to follow this methodology in my free time and implemented BInary Search and Rabin Miller primality testing .Being a new to Haskell i don’t have idea about efficient codes but it works.

Binary Search Single comparison per iteration Implementation.

bsearch :: [Integer]->Integer->Maybe Int bsearch ps k = let n=length ps t=bsearch_ 0 n where bsearch_ lo hi | lo>=hi = lo | ps!!mid <k = bsearch_ (mid+1) hi | otherwise = bsearch_ lo mid where mid = div (lo+hi) 2 in if (t< n && ps!!t==k) then Just t else Nothing

Rabin Miller Primality Testing

import System.Random fun :: Integer->(Integer,Integer) fun n = f 0 (n-1) where f d m | mod m 2 == 0 = f (d+1) (div m 2) | otherwise =(d,m) rabinmiller:: Integer-> Integer-> Bool rabinmiller n a | b0 == 1 || b0== (n-1) = True |otherwise = iter (tail b) where (d,m)=fun n b0= mod (a^m) n b = take (fromIntegral d) $ iterate (\x-> mod (x*x) n) b0 iter [] = False iter (x:xs) | x==1 = False | x==(n-1) = True | otherwise = iter xs primetest n | n<2 = False | n==2 = True | even n = False | otherwise =testfun n (take 5 $ randomRs (2,n-2) (mkStdGen 3) :: [Integer]) where --testfun n []= testfun n (x:xs) | tmp == False = False | tmp == True = True | otherwise = testfun n xs where tmp = rabinmiller n x

Here is slightly different implementation of Rabin MIller which takes only one iteration and bit efficient than previous one.

import System.Random fun2mk :: Integer->(Integer,Integer) fun2mk n = let (s,d)= f 0 (n-1) where f s d | mod d 2 ==0 = f (s+1) (div d 2) | otherwise = (s,d) in (s,d) rabinmiller :: Integer->Bool rabinmiller n | n<2 = False | n==2 = True | even n = False | b0==1 || b0== n' = True | otherwise = iter (tail b) where n'= n-1 (k,m)=fun2mk n a= head ( take 1 $ randomRs (2,n-2) (mkStdGen 3) :: [Integer]) b0 = mod (a^m) n b= take (fromIntegral k) $ iterate (\x-> mod (x*x) n) b0 iter []= False iter (x:xs) | x==1 = False | x==n'= True | otherwise = iter xs

If you want to run any of the program, save it as filename.hs. Now run GHCI from your command prompt [ i use linux but windows should be also similar ] and type :load filename.hs. If there is no error then it will load all the functions present in your file. To find out element in the list [ binary search in first code ] you can try bsearch [1..100] 10 and it will return the index of element 10. If element is not in the list and program will return Nothing.

If you find something wrong then let me know. I will try to improve the article.

!! operator takes O(n) time, so there is no any benefit from this implementation of binsearch. You should consider using Data.Array instead of a list.

Comment by hash | August 12, 2011 |

Yes you are correct. I wrote it long time ago when I was learning Haskell . Data.Array gives constant time access to elements so it is perfect for binary search. Thank you pointing out.

Comment by tiwari_mukesh | August 12, 2011 |

Cool, I was looking for a binary search in Haskell and this is one of the first things that shows up in a search. I’m going to try to convert your bsearch function to one that does a binary search on any ascending function (Ord a)=>(Int -> a), not just on lists or arrays. Seems like it should be pretty straightforward…

Comment by gcbenison | March 24, 2012 |