Interpolation Search

プログラミング

Interpolation Searchとは

  • 補間探索、内挿探索
  • 二分探索での範囲の中間値を利用する代わりに、範囲の両端の値から探したい値の位置にあたりをつけて、その値を利用して探索していく方法
    • 二分探索では、配列の値に関係なく範囲の中間の値を利用して探索
  • 探索時間はO(log log n)
    • 二分探索では、O(log n)
    • データに依っては、二分探索の方が速くなる場合もあり得る
計算例

配列vが「1,2,3,5,6,10,12」として、
left = 0, v[left] = 1
right = 6, v[right] = 12
である時、
2分探索では、mid = floor( (left + right) / 2 ) = floor( (0+6) / 2 ) = 3のように決めたりするが、
Interpolation Searchでは、値も考慮し、value=6を探したい場合、
mid = floor( left + (value - v[left]) * (right - left) / (v[right] - v[left]) ) = floor( 0 + (6-1) * (6-0) / (12-1) ) = 2のように決める。
計算的に、一様に値が分布していることを仮定して値の位置を計算しているので、一様であれば有効に働く。

コード

#include <iostream>
#include <vector>

template<class T>
class InterpolationSearch {
public:
  //配列vから値valueを探し、そのindexを返す
  //存在しない場合は-1を返す
  int search(const std::vector<T>& v, const T& value){
    if(v.size() == 0) return -1;

    int left = 0;
    int right = v.size()-1;
    
    if(left == right) return (v[left] == value) ? left : -1;
    if(value < v[left] || v[right] < value) return -1;

    while(true){
      int mid = (int)( left + (long long)(value - v[left]) * (right - left) / (v[right] - v[left]) );
      
      if(v[mid] == value){
        return mid;
      }
      else if(v[mid] < value){
        left = mid + 1;
      }
      else if(value < v[mid]){
        right = mid - 1;
      }
      if(value < v[left] || v[right] < value) break;
    }
    return -1;
  }
};


int main(){

  InterpolationSearch<int> is;

  //0〜99の、index == valueなソート済み配列を用意
  std::vector<int> v;
  for(int i=0; i<100; i++){
    v.push_back(i);
  }

  //配列から-1〜100を検索
  for(int i=-1; i<101; i++){
    std::cout << is.search(v, i) << std::endl;
  }

  return 0;
}

ところで文字列の場合、ソートはいいとしても、「値の差の大きさ」も必要になるので、どうするのがいいかなと思って調べてみたら、StackOverflowで同様の質問がでていた。
自明じゃないし、二分探索より遅くなる可能性もあるし、結局実用には難しいか・・・

参考