[Haskell-cafe] Performance question

[Arnoldo Muller]

Hello!

I am trying to implement a binary search function that returns the index of
an
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
array) .

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?

import Data.Array.IArray

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
    in
       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 !
mid
                               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


Thank you!

Arnoldo Muller
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100318/38296959/attachment.html