title: What is the fastest search method for a sorted array?
body: <p>Answering to <a href="https://stackoverflow.com/questions/4752028/whats-wrong-with-this-interpolation-search-implementation/4752042#4752042">another question</a>, I wrote the program below to compare different search methods in a sorted array. Basically I compared two implementations of Interpolation search and one of binary search. I compared performance by counting cycles spent (with the same set of data) by the different variants.</p>
  
  <p>However I'm sure there is ways to optimize these functions to make them even faster. Does anyone have any ideas on how can I make this search function faster? A solution in C or C++ is acceptable, but I need it to process an array with 100000 elements.</p>
  
  <pre><code>#include &lt;stdlib.h&gt;
  #include &lt;stdio.h&gt;
  #include &lt;time.h&gt;
  #include &lt;stdint.h&gt;
  #include &lt;assert.h&gt;
  
  static __inline__ unsigned long long rdtsc(void)
  {
    unsigned long long int x;
       __asm__ volatile (".byte 0x0f, 0x31" : "=A" (x));
       return x;
  }
  
  int interpolationSearch(int sortedArray[], int toFind, int len) {
      // Returns index of toFind in sortedArray, or -1 if not found
      int64_t low = 0;
      int64_t high = len - 1;
      int64_t mid;
  
      int l = sortedArray[low];
      int h = sortedArray[high];
  
      while (l &lt;= toFind &amp;&amp; h &gt;= toFind) {
          mid = low + (int64_t)((int64_t)(high - low)*(int64_t)(toFind - l))/((int64_t)(h-l));
  
          int m = sortedArray[mid];
  
          if (m &lt; toFind) {
              l = sortedArray[low = mid + 1];
          } else if (m &gt; toFind) {
              h = sortedArray[high = mid - 1];
          } else {
              return mid;
          }
      }
  
      if (sortedArray[low] == toFind)
          return low;
      else
          return -1; // Not found
  }
  
  int interpolationSearch2(int sortedArray[], int toFind, int len) {
      // Returns index of toFind in sortedArray, or -1 if not found
      int low = 0;
      int high = len - 1;
      int mid;
  
      int l = sortedArray[low];
      int h = sortedArray[high];
  
      while (l &lt;= toFind &amp;&amp; h &gt;= toFind) {
          mid = low + ((float)(high - low)*(float)(toFind - l))/(1+(float)(h-l));
          int m = sortedArray[mid];
  
          if (m &lt; toFind) {
              l = sortedArray[low = mid + 1];
          } else if (m &gt; toFind) {
              h = sortedArray[high = mid - 1];
          } else {
              return mid;
          }
      }
  
      if (sortedArray[low] == toFind)
          return low;
      else
          return -1; // Not found
  }
  
  int binarySearch(int sortedArray[], int toFind, int len) 
  {
      // Returns index of toFind in sortedArray, or -1 if not found
      int low = 0;
      int high = len - 1;
      int mid;
  
      int l = sortedArray[low];
      int h = sortedArray[high];
  
      while (l &lt;= toFind &amp;&amp; h &gt;= toFind) {
          mid = (low + high)/2;
  
          int m = sortedArray[mid];
  
          if (m &lt; toFind) {
              l = sortedArray[low = mid + 1];
          } else if (m &gt; toFind) {
              h = sortedArray[high = mid - 1];
          } else {
              return mid;
          }
      }
  
      if (sortedArray[low] == toFind)
          return low;
      else
          return -1; // Not found
  }
  
  int order(const void *p1, const void *p2) { return *(int*)p1-*(int*)p2; }
  
  int main(void) {
      int i = 0, j = 0, size = 100000, trials = 10000;
      int searched[trials];
      srand(-time(0));
      for (j=0; j&lt;trials; j++) { searched[j] = rand()%size; }
  
      while (size &gt; 10){
          int arr[size];
          for (i=0; i&lt;size; i++) { arr[i] = rand()%size; }
          qsort(arr,size,sizeof(int),order);
  
          unsigned long long totalcycles_bs = 0;
          unsigned long long totalcycles_is_64 = 0;
          unsigned long long totalcycles_is_float = 0;
          unsigned long long totalcycles_new = 0;
          int res_bs, res_is_64, res_is_float, res_new;
          for (j=0; j&lt;trials; j++) {
              unsigned long long tmp, cycles = rdtsc();
              res_bs = binarySearch(arr,searched[j],size);
              tmp = rdtsc(); totalcycles_bs += tmp - cycles; cycles = tmp;
  
              res_is_64 = interpolationSearch(arr,searched[j],size);
              assert(res_is_64 == res_bs || arr[res_is_64] == searched[j]); 
              tmp = rdtsc(); totalcycles_is_64 += tmp - cycles; cycles = tmp;
  
              res_is_float = interpolationSearch2(arr,searched[j],size);
              assert(res_is_float == res_bs || arr[res_is_float] == searched[j]); 
              tmp = rdtsc(); totalcycles_is_float += tmp - cycles; cycles = tmp;
          }
          printf("----------------- size = %10d\n", size);
          printf("binary search          = %10llu\n", totalcycles_bs);
          printf("interpolation uint64_t = %10llu\n",  totalcycles_is_64);
          printf("interpolation float    = %10llu\n",  totalcycles_is_float);
          printf("new                    = %10llu\n",  totalcycles_new);
          printf("\n");
          size &gt;&gt;= 1;
      }
  }
  </code></pre>