Ruby 无限循环的插值搜索实现

Question

我刚刚学会了如何进行插值搜索，但在 Ruby 上的实现有问题。我一直有无限循环，下限或上限接近搜索到的数字，但下限不触及方法退出条件的上限。

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

您也可以 return 索引或 nil 而不是 true 或 false。

Ruby 无限循环的插值搜索实现

Interpolation Search Implementation on Ruby Infinite Loop

ruby

binary-search

linear-interpolation

备注

解决方案