[Haskell-cafe] Performance question
arnoldomuller at gmail.com
Thu Mar 18 14:59:33 EDT 2010
I am trying to implement a binary search function that returns the index of
exact or the (index + 1) where the item should be inserted in an array if
the item to be searched is not found (I am not trying to insert data in the
Right now, the bottleneck of my program is in binarySearch', the function
must be called a few billion times.
Do you have any ideas on how to improve the performance of this function?
type IntArray a = Array Int a
-- The array must be 0 indexed.
binarySearch :: Ord a => a -> IntArray a -> Int
binarySearch query array =
let (low, high) = bounds array
binarySearch' query array low high
binarySearch' :: Ord a => a -> IntArray a -> Int -> Int -> Int
binarySearch' query array !low !high
| low <= high = let ! mid = low + ((high - low) `div` 2)
! midVal = array !
in next mid midVal
| otherwise = -(low + 1)
where next mid midVal
| midVal < query = binarySearch' query array (mid + 1) high
| midVal > query = binarySearch' query array low (mid - 1)
| otherwise = mid
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe