C Interpolated Search Source

Algorithms in C - search.c

<source lang="c"> /* Find function using predictive search and sequential search. Assumes list */ /* has been sorted. Searches between lower_index and upper_index. Returns */ /* index in list for value or -1 if not found. Calls itself recursively. */ int find( const int* list, const int value, int lower_index, int upper_index ) {

  const int SMALL_LIST_LENGTH = 16;
  
  const int low_index_value = list[ lower_index ];
  const int search_space = upper_index - lower_index;

  int i;
  int found_index = -1;
  int estimated_index;
  int estimated_index_value;
  float estimated_fraction;

  /* If only a small part of the list remains use sequential search */
  if( search_space <= SMALL_LIST_LENGTH )
  {
     for( i = lower_index; i <= upper_index && found_index == -1; i++ )
     {
        if( list[i] == value )
           found_index = i;
     }
  }
  else
  {
     /* Guess the index where the value will be (assume even distribution) */
     estimated_fraction = ( value - low_index_value ) /
                              (float)( list[ upper_index ] - low_index_value );

     /* If the value is outside the list, return -1 */
     if( estimated_fraction < 0 || estimated_fraction > 1 )
        return -1;

     /* Get the value at the estimated index point */
     estimated_index = (int)( estimated_fraction * search_space ) +lower_index;

     estimated_index_value = list[ estimated_index ];

     if( estimated_index_value < value )
     {
        /* If the value at this point is too low, look higher */
        found_index = find( list, value, estimated_index + 1, upper_index );
     }
     else if( estimated_index_value > value )
     {
        /* If the value at this point is too high, look lower */
        found_index = find( list, value, lower_index, estimated_index - 1 );
     }
     else
     {
        /* If the value is not too high or too low, we have found it */
        found_index = estimated_index;
     }
  }

  return found_index;

} </source>