爲什麼此插值搜索算法僅適用於1位數值？ （不適用於大於10的密鑰）

Question

#include <iostream> 
#include <string> 

using namespace std; 



int main() 
{ 
    int arr[] = {1,3,5,7,9,11,13,15,17,19,21}; 
    int first, last, pos, key; 

    first = 0; 
    last = (sizeof(arr)/ sizeof(arr[0])) - 1; 
    cout << "Enter the key value:\t" << endl; 
    cin >> key; 

    //The search code starts from here 
    while(first <= last && key >= first && key <= last) { 
     pos = first + (((last - first)/(arr[last] - arr[first])) * (key - arr[first])); 

     if(key < arr[pos]) { 
      last = pos - 1; 
     } 
     else if(key > arr[pos]) { 
      first = pos + 1; 
     } 
     else { 
      cout << "Found the value at index:\t" << pos << endl; 
      break; 
     } 
    } 

    //if the value is not found 
    if(first > last) { 
     cout << "The value is not found." << endl; 
    } 
    return 0; 
} 

該算法的工作原理從零到10.但是，無論何時輸入11或更多，代碼都會以某種方式泄漏，這是我無法弄清楚的。我是編程新手，因此我面臨一些困難。

謝謝你的時間。

Answer 1

問題是，當你除以兩個整數值時，如果第一個值（分子）小於第二個（分母），你會得到零。然後你需要先通過乘法來增加分子的值。嘗試使用此代碼：

pos = first + (last - first) * (key - arr[first])/(arr[last] - arr[first]); 

還是老老實實用浮點計算：

//The search code starts from here 
while(first <= last && key >= first && key <= last) { 
    pos = (int)((double)first + (double)(last - first) * (double)(key - arr[first])/(double)(arr[last] - arr[first])); 

    if(key < arr[pos]) { 
     last = pos - 1; 
    } 
    else if(key > arr[pos]) { 
     first = pos + 1; 
    } 
    else { 
     cout << "Found the value at index:\t" << pos << endl; 
     break; 
    } 
}