Как реализовать приближенный двоичный поиск?

Question

[sasha_zaitsev]

Реализуйте алгоритм приближенного бинарного поиска.
Входные данные
В первой строке входных данных содержатся числа N и K (0NK100001 ). Во второй строке задаются N чисел первого массива, отсортированного по неубыванию, а в третьей строке – K чисел второго массива. Каждое число в обоих массивах по модулю не превосходит 2*10^9.
Выходные данные
Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному. Если таких несколько, выведите меньшее из них.
Где ошибка?

const q=100000;
type s = array[1..q] of integer;                                                                        
var mas,mas2: s;
var n,k,i,l,r,c: integer;
begin
readln(n,k);
for i:=1 to n do read(mas[i]);
for i:=1 to k do read(mas2[i]);
for i:=1 to k do
   begin
   l:=1;
   r:=n+1;
   while l<r-1 do
      begin
      c:=(l+r) div 2;
      if mas2[i]<mas[c] then
         r:=c
      else
         l:=c;
      end;
   if l<>r then
     begin
      if abs(mas[r]-mas2[i])<abs(mas[l]-mas2[i]) then
         writeln(mas[r])
      else writeln(mas[l]);
     end
    else writeln(mas[l])
   end;
end.

Answer 1

[jcmvbkbc]

Как минимум ваш двоичный поиск может закончиться с r = n+1, из-за чего код в if l <> r не будет работать.

Comments

[sasha_zaitsev]

Исправил на r:=n;. Есть еще ошибки?

[jcmvbkbc]

n+1 было правильно, иначе будет неправильно работать для искомого числа, большего всех элементов массива.
В конце надо проверить, есть ли что-нибудь справа от l или нет.

[jcmvbkbc]

а, хотя да, с r := n тоже должно работать.

[sasha_zaitsev]

jcmvbkbc: c r:=n; работает,но где-то есть ошибка т.к. не проходит один тест(

[jcmvbkbc]

abs(mas[r]-mas2[i]) и abs(mas[l]-mas2[i]) выглядят сомнительно. В том смысле, что разности в скобках могут переполнить 32-битный знаковый integer. Т.е. в массиве 1500000000, 2000000000 для числа -1500000000 будет найдено 2000000000.

[sasha_zaitsev]

jcmvbkbc: c uint64 тоже не работает

[jcmvbkbc]

а почему uint?

[sasha_zaitsev]

и с int64 тоже

Answer 2

[Mercury13]

Алгоритм такой.
1. Реализуй двоичный поиск с указанием места, куда вставить (см. Википедию).
2. Если вставить до первой позиции или за последнюю — return соотв. первое или последнее число.
3. В противном случае выяснить, какое ближе из (i−1)-го и i-го.

Дома проверю, где там ошибка в двоичном поиске, в нём любят ошибаться.

К тому же код у вас чисто олимпиадный, я бы отделил рабочую логику от генерации выходного файла.

Comments

[jcmvbkbc]

Дома проверю, где там ошибка в двоичном поиске, в нём любят ошибаться.

Ну как?