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&#39;, 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 =&gt;  a -&gt;  IntArray a  -&gt; Int<br>binarySearch query array = <br>    let (low, high) = bounds array<br>    in<br>       binarySearch&#39; query array low high<br>
<br><br>binarySearch&#39; :: Ord a =&gt;  a -&gt;  IntArray a -&gt; Int -&gt; Int -&gt; Int<br>binarySearch&#39; query array !low !high<br>    | low &lt;= 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 &lt; query = binarySearch&#39; query array  (mid + 1) high<br>               |  midVal &gt; query = binarySearch&#39; query array  low  (mid - 1)<br>
               |  otherwise = mid <br><br><br>Thank you!<br><br>Arnoldo Muller<br>