Другие языки программирования и технологии

ПОМОГИТЕ НАЙТИ ОШИБКУ!

Реализуйте алгоритм бинарного поиска.

Входные данные
В первой строке входных данных содержатся натуральные числа N и K (0NK100000). Во второй строке задаются N элементов первого массива, отсортированного по возрастанию, а в третьей строке – K элементов второго массива. Элементы обоих массивов - целые числа, каждое из которых по модулю не превосходит 109

Выходные данные
Требуется для каждого из K чисел вывести в отдельную строку "YES", если это число встречается в первом массиве, и "NO" в противном случае.

Примеры
входные данные
10 5
1 2 3 4 5 6 7 8 9 10
-2 0 4 9 12
выходные данные
NO
NO
YES
YES
NO

#include
#include
#include
using namespace std;
int main()
{
int n,k,i,g,a[n],b[k],r=1000000000,l=1,x;
cin>>n>>k;
for (i=0;i>a[i];
cout<<a[i];
}
for (g=0;g>b[g];
cout<<b[g];
}
{
while (l<r)
{
x=(r+l)/2;
if (a[x]<b[g]) l=x+1;
else r=x;
}
if (a[l]==x) cout<<"Yes";
else cout<<"No";
}
}
М.
Макс .
459
n и k не инициализированы и содержат мусор, а вы этими значениями резервируете память, а потом вводите их же. Миллиард - это максимальное и минимальное значение элементов, а не размер массива. С таким r есть выход за пределы . А самое главное - всё остальное нечитабельно, ибо, похоже, вы код поместили туда, где должен изменяться счётчик цикла, скобки друг другу не соответствуют. Исправил ваш код. Второй массив убрал, так как на ходу можно ответ выводить, ведь, судя по примеру, проверяет решение не человек. И да, в таком случае печатать можно только то, что требует тест, строго соблюдая форматирование. Также, не советую большие массивы на стеке заводить.

#include <iostream>

using namespace std;

int main() {
int a[100000], n, k;
cin >> n >> k;

for (int i = 0; i < n; i++)
cin >> a[i];

for (int i = 0; i < k; i++) {
int item;
cin >> item;
int l = 0, r = n, x = 0;

while (l < r) {
x = l + (r - l) / 2;
if (a[x] == item)
break;
else if (a[x] < item)
l = x + 1;
else
r = x;
}
cout << (a[x] == item ? "YES" : "NO") << '\n';
}

}
Хусрав Якубов
Хусрав Якубов
20 861
Лучший ответ
Макс . А почему в x = l + (r - l) / 2;
идёт "+l"