Hello!<br><br>I am trying to implement a binary search function that returns the index of an<br>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) . <br>
<br>Right now, the bottleneck of my program is in binarySearch', the function must be called a few billion times.<br><br>Do you have any ideas on how to improve the performance of this function? <br><br>import Data.Array.IArray<br>
<br>type IntArray a = Array Int a<br><br>-- The array must be 0 indexed.<br>binarySearch :: Ord a => a -> IntArray a -> Int<br>binarySearch query array = <br> let (low, high) = bounds array<br> in<br> binarySearch' query array low high<br>
<br><br>binarySearch' :: Ord a => a -> IntArray a -> Int -> Int -> Int<br>binarySearch' query array !low !high<br> | low <= high = let ! mid = low + ((high - low) `div` 2) <br> ! midVal = array ! mid <br>
in next mid midVal <br> | otherwise = -(low + 1)<br> where next mid midVal <br> | midVal < query = binarySearch' query array (mid + 1) high<br> | midVal > query = binarySearch' query array low (mid - 1)<br>
| otherwise = mid <br><br><br>Thank you!<br><br>Arnoldo Muller<br>