Interpolation search

The interpolation search, also called interval search, is a derivative of the binary search search method that comes to lists and fields are used.

While the algorithm of the binary search is always checked the middle element of the search space, the algorithm of the interpolation search in the search space tries to guess a better division point as the center. The operation is similar to that of a human, in need of a word in a dictionary: Finding cylinder is usually started at the end of the dictionary, while searching for eel in the front area is likely to be started.

The algorithm

The Interpolation is based on sorted data. It is best suited for uniformly distributed data. It also assumes a random access to the elements. The data will be shared with the Interpolation function of the key. Did this a great value, the desired element is due to the sorting in the rear part of the data. Accordingly, the division is carried out also in the rear part of the data. With a small key, the field is divided in accordance with the front part.

For all data can be the dividing position calculated by first determining the total number of items divided by the number of different elements, and is then multiplied with the desired key:

The position of this element is thus interpolated by the equal distribution of data for an image of the key to the list or the field is used.

Can now be checked whether the key of the dividing element has a larger or smaller value as the key of the desired element. With identical keys, the search has ended. If the dividing element has a smaller value, and the right portion is further examined, otherwise, the left portion. The number of elements and the number of different key is determined for the new area, and then interpolates a new indexing position.

Example

A short practical example is provided to illustrate the operation of interpolation search. For this purpose, the value 7 into the following elements is sought:

Initially, the left (L ) and right ( r) is set to limit the boundaries of the array. Then, the partition member is calculated using the following formula:

This is so for the array (red = search area, blue = x, bold = wanted ):

Then, looked to see whether the item found is the sought. If this is the case, can be interrupted, otherwise the search range is limited. If the selected x for small - so you have to look right - the left boundary is set to x 1 and searched it. The right boundary at x - - Otherwise - so you have to look to the left (or the x is too large) set 1 and now the left side looking for.

Since the value of A = 4 is less than the desired element is in the left limit L = x 1 = 3. The right border remains and it results in the following formula:

The list now looks like this:

Since A is [x] = A = 7 = v, that is, the element is found, it can be canceled and returned to x as a solution in two steps.

Complexity

A study of interpolation search is proving to be very complex, as the runtime, however, (n is the number of elements ) are accepted in the average case. In the worst case ( the interpolated expected position is always at the edge ), the term is, however. This impairment solves the Quadratic binary search.

Example implementations

VB.NET 2008

' Instead of a List (Of Integer) could also IEnumerable ( Of Integer ), etc. can be used. IEnumerable allows the transfer    ' both of generic lists, and arrays    Public Function InterpolatedSearch (ByVal key As Integer, ByVal array As List ( Of Integer ) ) As Integer      Dim left As Integer = 0      Dim right As Integer = array.Count - 1      Dim diffElem, pos As Integer        Do While (key > = array (left) ) AndAlso (key < = array (right) )        diffElem = array (right) - array ( left )        pos = left Math.Floor ( ( right - left ) * ( key - array ( left )) / diffElem )        If key > array (pos ) Then          left = pos 1        ElseIf key < array ( pos)          right = pos - 1        else          Return pos        end If      loop      Return -1    end Function Java

Public int interpolated looking for (int schluessel, int data [] ) {      int left = 0; / / Left part of field boundary      int right = daten.length - 1; / / Right part of the field boundary      int various nationalities; / / Number of different elements      int pos; / / Current indexing position        / / As long as the key is in the range (otherwise the desired      / / Element does not exist )      while ( schluessel > = data [ left ] && schluessel < = data [ right] ) {        / / Update the number of different elements        of various = data [ right] - data [ left ];          / / Calculate the new interpolated pitch position        pos = left (int ) (( (double) right - left ) * ( schluessel - data [ left ] )              / Various nationalities );          if ( schluessel > data [ pos] ) / / right subinterval          left = pos 1; / / Data [ pos] already checked        else if ( schluessel < data [ pos] ) / / left subinterval          right = pos - 1; / / Data [ pos] already checked        found else / / element          return pos; / / Return position      }        return -1; Not found / / element    } Delphi

Grade    TIntArray = array of integer;   function interpolated search ( schluessel: integer; var data: TIntArray ): integer; var    left, right,    various nationalities, APOS: integer; begin    left: = 0;    right: = high (data);    various nationalities: = 0;    APOS: = 0;    while ( schluessel > = data [ left ] ) and ( schluessel < = data [ right] ) do    begin      various nationalities: = data [ right] - data [ left ];      APOS: = left round ( ( right - left ) * ( schluessel - data [ left ] ) / various nationalities );      if ( schluessel > data [ apos ] ) then        left: = APOS 1 else          if ( schluessel < data [ apos ] ) then            right: = apos - 1 else            begin              result: = apos;              exit;            end;    end;    result: = - 1; end; C

/ **   * Returns 1 if X was found in M, 0 otherwise   * When called as fourth argument is a variable by address   * Passed in the position of X in M is written on success.   * @ Param const int [ ] M field, is to be sought in the   * @ Param int n size of the field   * @ Param int X of the searched entry   * @ Param int * index position of the entry X in M   * @ Return int 1 = found, 0 = not found   * / int interpolation_search (const int M [ ], int n, int X, int * index) {   double dx, dy;   double m; / / Slope   double b; / / Y-intercept   int left = 0; / / X1   int right = n-1; / / X2   int pos; / / Assumed position     if ( M == null | | X < M | | X > R [n -1])   {    return 0;   }     while ( left < = right)   {    dx = Right - Left;      if ( dx == 1)    {     if ( M [ right] == X)     {      * index = right;      return 1;     }     else if ( M [ left ] == X)     {      * index = left;      return 1;     }     return 0;    }      if ( dx == 0) / / 0 Division prevent    {     return 0;    }      dy = M [ right] - M [ left ];      if ( dy == 0) / / no slope    {     if ( M [ left ] == X)     {      * index = left;      return 1;     }     else     {      return 0;     }    }      m = dy / dx; / / Slope      b = (X - M [ left ] ) / m;      pos = left b; / / Calculate Assumed position      if ( M [pos ] == X)    {     * index = pos;     return 1;    }    else if ( M [pos ]> X)    {     right = pos - 1;    }    else    {     left = pos 1;    }   }   return 0; } literature

Robert Sedgewick: Algorithms in C. Addison -Wesley, Bonn 1992, ISBN 3-89319-376-6, pp. 239-241.