本页使用了标题或全文手工转换

插值搜尋

维基百科,自由的百科全书
跳到导航 跳到搜索
插值搜尋
分类 搜索算法
数据结构 數组
最坏时间复杂度
最优时间复杂度
平均时间复杂度
最坏空间复杂度

插值搜尋法(Interpolation search)是利用插值公式來計算猜測搜尋鍵值的位置。搜尋方式與二分搜尋相同。 [1]

插值公式:

插值 = (設算數 -­ 最小數) / (最大數 -­ 最小數): [2]

搜尋鍵值 = left + parseInt( ( key - data[left] ) / ( data[right] - data[left] ) )*( right - left ) )

演算法[编辑]

插值搜尋之演算法與二分搜尋演算法幾乎完全相同,差別在:

二分搜尋法:猜測鍵值在中間位置(middle)

插值搜尋法:用插值公式計算鍵值位置

時間複雜度[编辑]

二分搜尋在一般的情況下時間複雜度是對數時間,進行次比較操作(在此處是數組的元素數量,大O記號對數)。 [3]

插值搜尋的最壞時間複雜度是,平均進行次比較操作[4]。因為用插值公式計算搜尋鍵值,能使搜尋範圍比二分法更快縮小。所以除非輸入數據數量很少,否則插值搜尋比二分搜尋與線性搜尋更快,但數組必須事先被排序。無論對任何大小的輸入數據,插值搜尋演算法使用的空間複雜度一樣是

實作[编辑]

JS code: [5]

var interpolationSearch = function(data, key){
    var left = 0;
    var right = data.length - 1;
    var m = 0;
    while(left <= right){
        var m = parseInt((right - left)*(key - data[left])/(data[right] - data[left])) + left;
        if( m < left || m > right)
            break;
        if(key < data[m])
            right = m - 1;
        else if(key > data[m])
            left = m + 1;
        else
            return m;			
    }
    return -1;
};

//執行
var data = getRandomData();
quickSort(data, 0, data.length-1);
interpolationSearch(data, 5);        // (data, key)

参考资料[编辑]

  1. ^ YehYeh. 插補搜尋法(Interpolation Search). 
  2. ^ {{插值排序}}
  3. ^ {{二分搜尋演算法}}
  4. ^ Andersson, Arne, and Christer Mattsson. ‘Dynamic Interpolation Search in o(log log n) Time’. In Automata, Languages and Programming, edited by Andrzej Lingas, Rolf Karlsson, and Svante Carlsson, 700:15–27. Lecture Notes in Computer Science. Springer Berlin / Heidelberg, 1993. doi:10.1007/3-540-56939-1_58
  5. ^ YehYeh. 插補搜尋法(Interpolation Search).