Для каждого из 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
закрываются.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д