Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному

@Maxim35 · Регистрация: 29.05.2016

Author24 — интернет-сервис помощи студентам

Здравствуйте,помогите пожалуйста написать код,спасибо.Реализуйте алгоритм приближенного бинарного поиска.

Входные данные
В первой строке входных данных содержатся числа N и K (0NK100001 ). Во второй строке задаются N чисел первого массива, отсортированного по неубыванию, а в третьей строке – K чисел второго массива. Каждое число в обоих массивах по модулю не превосходит 2109.

Выходные данные
Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному. Если таких несколько, выведите меньшее из них.

Примеры
входные данные
5 5
1 3 5 7 9
2 4 8 1 6
выходные данные
1
3
7
1
5

@Puporev · 13.06.2016, 12:15

Вот для подсказки пример приближенного бинарного поиска.

Pascal

const n=5;
      k=4;
      a:array[1..n] of integer=(1,4,5,8,10);
      b:array[1..k] of integer=(5,6,1,9);
var i,j,l,r,m:integer;
begin
for i:=1 to n do
write(a[i]:3);
writeln;
for i:=1 to k do
write(b[i]:3);
writeln;
for i:=1 to k do
 begin
  l:=1;
  r:=n;
  for j:=1 to n do
   begin
    m:=(l+r) div 2;
    if a[m]>b[i] then r:=m else l:=m;
   end;
    if l<>r then
     begin
      if abs(a[r]-b[i])<abs(a[l]-b[i]) then writeln(a[r])
      else writeln(a[l]);
     end
    else writeln(a[l])
 end;
end.

@bormant · 13.06.2016, 12:49

Если что,

Pascal

17	for j:=1 to n do

убивает напрочь преимущества бинарного поиска, состоящие в сокращении количества просмотров.

@Puporev · 13.06.2016, 12:55

Да, извиняюсь, взял не глядя какой-то свой древний код.

@Maxim35 0 / 0 / 0 Регистрация: 29.05.2016 Сообщений: 27
		1
	Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному 13.06.2016, 11:36. Показов 3800. Ответов 3 Метки pascalabc (Все метки) Здравствуйте,помогите пожалуйста написать код,спасибо.Реализуйте алгоритм приближенного бинарного поиска. Входные данные В первой строке входных данных содержатся числа N и K (0NK100001 ). Во второй строке задаются N чисел первого массива, отсортированного по неубыванию, а в третьей строке – K чисел второго массива. Каждое число в обоих массивах по модулю не превосходит 2109. Выходные данные Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному. Если таких несколько, выведите меньшее из них. Примеры входные данные 5 5 1 3 5 7 9 2 4 8 1 6 выходные данные 1 3 7 1 5 0

@Puporev Почетный модератор 64300 / 47595 / 32743 Регистрация: 18.05.2008 Сообщений: 115,181
	13.06.2016, 12:55	4
	Да, извиняюсь, взял не глядя какой-то свой древний код. 0

Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному

Решение