title: interpolation search array out of bounds
body: <p>I am making a java program that uses the interpolation search below I have gotten from wikipedia. In my main program I have created an int array that will have 100,000 spots. Then I fill all those spots with random numbers and sort it. I then generate a random search key and call the function. I am also looping the function call 100 times each time with a different search key. When I do this I get an array out of bounds error on this statement if (sortedArray[mid] &lt; toFind). The program works fine with an array with 10 spots, 100 spots, 1000 spots, but when I get to 100,000 I get the error. Do you know what I can do to fix this problem?</p>
  
  <pre><code> public int interpolationSearch(int[] sortedArray, int toFind){
    // Returns index of toFind in sortedArray, or -1 if not found
    int low = 0;
    int high = sortedArray.length - 1;
    int mid;
  
    while (sortedArray[low] &lt;= toFind &amp;&amp; sortedArray[high] &gt;= toFind) {
     mid = low +
           ((toFind - sortedArray[low]) * (high - low)) /
           (sortedArray[high] - sortedArray[low]);  
  
     if (sortedArray[mid] &lt; toFind)
      low = mid + 1;
     else if (sortedArray[mid] &gt; toFind)
      // Repetition of the comparison code is forced by syntax limitations.
      high = mid - 1;
     else
      return mid;
    }
  
    if (sortedArray[low] == toFind)
     return low;
    else
     return -1; // Not found
   }
  </code></pre>