Ruby 对二维数组的第 2 个元素进行插值搜索

Question

下面是对一维数组 $employee_list 的简单插值搜索。该列表是员工 ID 的有序列表，可能因退休而存在间隙。

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

现在我想向列表中添加一个新元素，数组的第二个元素将包含员工出生年份（即 $employee_list[id][birthyear]）。我可以根据出生年份对数组进行排序，我想根据出生年份和 return 具有该特定出生年份的员工 ID 列表执行插值搜索。

Answer 1

给出以下 employee_list：

employee_list = [[19, 1992], [41, 1985], [12, 1958], [63, 1985]]

如果想得到1985年出生的员工的ids只需要select那些最后一个元素是1985的数组，然后得到过滤后的数组的第一个元素：

employee_list.select{|employee| employee.last == 1985}.map(&:first)
# => [41, 63]

Answer 2

这是修改后的版本。 returns one id 如果找到给定年份的员工，如果没有找到员工 nil。

如果您一年需要 return 多个 ID，则需要修改版本的插值搜索。最后，插值搜索最适合均匀分布的值。我猜员工的生日真的不是这样。

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

employee_list = Array.new(10) {|i| [i, rand(1990..2000)] }.sort_by(&:last)

p employee_list
#=> [[5, 1990], [8, 1990], [2, 1991], [9, 1991], [7, 1992], [0, 1995], [6, 1996], [4, 1998], [1, 1999], [3, 1999]]
#=> [[8, 1990], [4, 1991], [5, 1991], [6, 1991], [2, 1996], [0, 1998], [1, 1998], [3, 1998], [7, 1999], [9, 2000]]

p find_id_for_year(employee_list, 1992)
#=> 7
#=> nil

Ruby 对二维数组的第 2 个元素进行插值搜索

Ruby Interpolation Search on 2nd Element of a Two Dimensional Array

ruby

arrays

sorting

multidimensional-array

linear-interpolation