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