아래에있는 것은 1 차원 배열에 대한 간단한 보간 검색입니다 $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]. 출생 연도를 기준으로 배열을 정렬 할 수 있으며 출생 연도를 기준으로 보간 검색을 수행하고 특정 출생 연도를 가진 직원 ID 목록을 반환하고 싶습니다.
다음은 수정 된 버전입니다. 주어진 연도의 직원이 발견되고 직원이 발견되지 않은 경우 하나를 반환합니다 .idnil
1 년 동안 여러 개의 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
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다