Для каждого из K чисел вывести в отдельную строку "YES", если число встречается в первом массиве - Pascal
Формулировка задачи:
Здравствуйте,помогите пожалуйста написать код,спасибо.Реализуйте алгоритм бинарного поиска.Входные данные
В первой строке входных данных содержатся натуральные числа 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
Решение задачи: «Для каждого из K чисел вывести в отдельную строку "YES", если число встречается в первом массиве»
textual
Листинг программы
var a : array [1..100000] of Longint; n, k, i, z, first, last, mid : Longint; fin, fout : Text; begin Assign(fin, 'input.txt'); Assign(fout, 'output.txt'); Reset(fin); Rewrite(fout); ReadLn(fin, n, k); for i := 1 to n do Read(fin, a[i]); ReadLn(fin); for i := 1 to k do begin Read(fin, z); if (z < a[1]) or (z > a[n]) then WriteLn(fout, 'NO') else begin first := 1; last := n + 1; while first <> last do begin mid := first + (last - first) div 2; if z <= a[mid] then last := mid else first := mid + 1; end; if a[last] = z then WriteLn(fout, 'YES') else WriteLn(fout, 'NO'); end; end; Close(fin); Close(fout); end.
Объяснение кода листинга программы
- Объявляется массив
aиз 100000 элементов типа Longint. - Объявляются переменные
nиkтипа Longint, а также переменныеi,z,first,last,mid. - Объявляются файлы
finиfoutдля ввода и вывода. - Открывается файл
input.txtдля чтения иoutput.txtдля записи. - Считывается количество чисел
nиkиз файлаinput.txt. - Для каждого числа от 1 до
nсчитывается элементa[i]из файлаinput.txt. - Для каждого числа от 1 до
kсчитывается числоzиз файлаinput.txt. - Если число
zменьше первого элемента массиваaили больше последнего элемента массиваa, выводитсяNO. - Если число
zнаходится в пределах массиваa, происходит поиск бинарным методом. - Пока переменные
firstиlastне равны друг другу, вычисляется средний индексmidи происходит сравнение числаzс элементомa[mid]. - Если число
zменьше или равно элементуa[mid], переменнойlastприсваивается значениеmid. - Если число
zбольше элементаa[mid], переменнойfirstприсваивается значениеmid + 1. - После завершения поиска, если элемент
a[last]равен числуz, выводитсяYES, иначе выводитсяNO. - Файлы
input.txtиoutput.txtзакрываются.