Ruby無限循環上的插值搜索實現

Question

我剛剛學會了如何進行插值搜索，但是在Ruby上的實現方面存在問題。我保持無限循環，下限或上限接近搜索的數字，但下限不會觸及方法退出條件的上限。

def exist?(id) 
 
\t lower = 0 
 
\t upper = $employee_list.length - 1 
 
\t while lower <= upper 
 
\t \t rise = upper - lower 
 
\t \t run = $employee_list[upper] - $employee_list[lower] 
 
\t \t x = id - $employee_list[lower] 
 
\t \t middle = (rise.to_f/run.to_f * x.to_f + lower.to_f).floor 
 
\t \t if id == $employee_list[middle] 
 
\t \t \t return true 
 
\t \t elsif id < $employee_list[middle] 
 
\t \t \t upper = middle - 1 
 
\t \t else 
 
\t \t \t lower = middle + 1 
 
\t \t end 
 
\t end 
 
end

Answer 1

注

• 如果lower等於upper，run是0，你用0

• 有沒有在你的代碼中沒有退出條件劃分。沒有理由lower比upper，所以它無限循環。

解決方案

我混你的代碼和一個mentionned here，它似乎很好地工作：

def exist?(array, key) 
    lower = 0 
    upper = array.length - 1 
    while array[upper] != array[lower] && key >= array[lower] && key <= array[upper] 
    middle = lower + ((key - array[lower]) * (upper - lower)/(array[upper] - array[lower])) 
    if key > array[middle] 
     lower = middle + 1 
    elsif key < array[middle] 
     upper = middle - 1 
    else 
     return true 
    end 
    end 
    key == array[lower] 
end 

exist?($employee_list, id) 

您還可以返回該指數或nil代替true或false。