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