Выполнение поиска интерполяции на бесконечной петле 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, поэтому он бесконечно петляет.

Решение

Я смешал свой код и один 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.