What is the fastest search method for a sorted array?

Question

Answering to another question, 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.

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.

#include <stdlib.h> #include <stdio.h> #include <time.h> #include <stdint.h> #include <assert.h>  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 <= toFind && h >= toFind) {         mid = low + (int64_t)((int64_t)(high - low)*(int64_t)(toFind - l))/((int64_t)(h-l));          int m = sortedArray[mid];          if (m < toFind) {             l = sortedArray[low = mid + 1];         } else if (m > 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 <= toFind && h >= toFind) {         mid = low + ((float)(high - low)*(float)(toFind - l))/(1+(float)(h-l));         int m = sortedArray[mid];          if (m < toFind) {             l = sortedArray[low = mid + 1];         } else if (m > 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 <= toFind && h >= toFind) {         mid = (low + high)/2;          int m = sortedArray[mid];          if (m < toFind) {             l = sortedArray[low = mid + 1];         } else if (m > 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<trials; j++) { searched[j] = rand()%size; }      while (size > 10){         int arr[size];         for (i=0; i<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<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 >>= 1;     } } 

Answer 1

If you have some control over the in-memory layout of the data, you might want to look at Judy arrays.

Or to put a simpler idea out there: a binary search always cuts the search space in half. An optimal cut point can be found with interpolation (the cut point should NOT be the place where the key is expected to be, but the point which minimizes the statistical expectation of the search space for the next step). This minimizes the number of steps but... not all steps have equal cost. Hierarchical memories allow executing a number of tests in the same time as a single test, if locality can be maintained. Since a binary search's first M steps only touch a maximum of 2**M unique elements, storing these together can yield a much better reduction of search space per-cacheline fetch (not per comparison), which is higher performance in the real world.

n-ary trees work on that basis, and then Judy arrays add a few less important optimizations.

Bottom line: even "Random Access Memory" (RAM) is faster when accessed sequentially than randomly. A search algorithm should use that fact to its advantage.