補間検索

#include <cassert> 

/*
arr[low, high)がソートされ、この配列内のデータ「キー」を検索します。
「キー」が見つかった場合は、対応するインデックスを返します（必ずしも最高のインデックスとは限りません）。
「キー」が見つからない場合は、low - 1 を返します。

アルゴリズムが正しいことをどうやって確認するのでしょうか?
証拠：
（有限性：1回のループ後、[low, high]の幅は厳密に減少します）

拳、高 <--- 高 - 1
シナリオ1. 低 = 高の場合
シナリオ2. low < highの場合、arr[low] = arr[high]
シナリオ 3. low < high、arr[low] < arr[high]、key < arr[low]、または key > arr[high] の場合
シナリオ 4. low < high、arr[low] < arr[high]、arr[low] <= key <= arr[high] の場合

次にシナリオ 4 を分析してみましょう。
「while」ループに入ると、low <= middle <= high


    1回のループの後で（戻らない場合は）、"low > high" が発生するかどうかを分析します。
    1 ループ後:
        ケース a1: このループで「low」ブランチが実行されました
            arr[中央] < キー <= arr[高]
            つまり、中位＜高位
            このループの後には
            低 <= 高
        ケースa2: このループで「高」分岐が実行されました
            arr[low] <= key < arr[middle]
            つまり、低位<中位
            このループの後には
            低 <= 高

    1回のループの後（戻らない場合は）、"low <= high" になります。


    「while」ループを終了するとき:
        ケースb1: arr[low] >= arr[high]
            最後のループで「low」分岐が実行されると、
                arr[下限 - 1] < k <= arr[上限]
                arr[低] >= arr[高]
                低 <= 高
                だから我々は
                arr[low - 1] < k <= arr[low] = arr[high]
            最後のループで「high」分岐が実行されると、
                arr[low] <= キー < arr[high + 1]
                arr[低] >= arr[高]
                低 <= 高
                だから我々は
                arr[low] = arr[high] <= キー < arr[high + 1]

        ケースb2: (arr[low] < arr[high]) && (arr[low] > key):
            最後のループでは、「low」が変更されているはずです
            だから我々は
            arr[low - 1] < キー
            だから我々は
            arr[low - 1] < キー < arr[low]

        ケースb3: (arr[low] < arr[high]) && (key > arr[high])
            最後のループでは、「high」が変更されているはずです
            だから我々は
            キー < arr[高 + 1]
            だから我々は
            arr[low] < arr[high] < キー < arr[high + 1]

*/
テンプレート<型名T >  
静的ランクinterpolation_search_v001 ( T * arr 、const T & key 、ランク低、ランク高)          
{
    高さ-= 1 ;  
    int中間; 
    int initial_low =低い;   

    (( arr [低] < arr [高]) && ( arr [低] <=キー) && (キー< = arr [高])) {            
        中間=低+ ((キー- arr [低]) * (高-低)) / ( arr [高] - arr [低]);              

        アサート((低<=中) && (中<=高));      

        if ( arr [中央] <キー)   
            低=中+ 1 ;    
        そうでない場合(キー< arr [中間])    
            高=中- 1 ;    
        それ以外
            真ん中を返す; 
    }

    if (キー== arr [低])   
        低値を返す; 
    それ以外
        initial_low - 1を返します。   
}


/*
ソートされた配列 arr[low, high) で「キー」を検索します。
戻り値: arr[i] <= key となる最大のインデックス i

アルゴリズムが正しいことをどうやって確認するのでしょうか?
証拠：
有限性：1回のループの後、[low, high]の幅は厳密に減少する

拳、高 <---- 高 - 1
シナリオ1. 低 = 高の場合
シナリオ2. low < high、key < arr[low]、またはarr[high] <= keyの場合
シナリオ3. low < high の場合、arr[low] <= key < arr[high]

次にシナリオ 3 を分析してみましょう。
「while」ループに入ると、low <= middle < high

「while」ループを終了するとき:
    ケースa1: キー < arr[low]
        最後のループで「low」が変更されたので、
        arr[low - 1] <= キー < arr[low]
    ケースa2: arr[high] <= key
        最後のループで「high」が変更されたので、
        キー < arr[high]、不可能

結論: 「low - 1」を返す必要があります

*/
テンプレート<型名T >   
静的ランクinterpolation_search_v002 ( T * arr 、const T & key 、ランク低、ランク高) {           
    高さ-= 1 ;  
    アサート(低<=高);  
    ランク中位; 

    if (キー< arr [低]) {   
        low - 1を返します。   
    } 
    if ( arr [高] <=キー) {   
        高く返す; 
    }

    // 現在 low < high 、 arr[low] <= key < arr[high]
    while (( arr [低] <=キー) && (キー< arr [高] )) {        
        中間=低+ ((高-低) * (キー- arr [低])) / ( arr [高] - arr [低]);              

        アサート((低<=中) && (中<高));      

        if (キー< arr [中間]) {   
            高=中;  
        }それ以外{  
            低=中+ 1 ;    
        } 
    }

    low - 1を返します。   
}