Для каждого из 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
Листинг программы
  1. var
  2.   a : array [1..100000] of Longint;
  3.   n, k, i, z, first, last, mid : Longint;
  4.   fin, fout : Text;
  5. begin
  6.   Assign(fin, 'input.txt'); Assign(fout, 'output.txt');
  7.   Reset(fin); Rewrite(fout);
  8.  
  9.   ReadLn(fin, n, k);
  10.   for i := 1 to n do Read(fin, a[i]); ReadLn(fin);
  11.  
  12.   for i := 1 to k do
  13.     begin
  14.       Read(fin, z);
  15.       if (z < a[1]) or (z > a[n]) then
  16.         WriteLn(fout, 'NO')
  17.       else
  18.         begin
  19.           first := 1; last := n + 1;
  20.           while first <> last do
  21.             begin
  22.               mid := first + (last - first) div 2;
  23.               if z <= a[mid] then
  24.                 last := mid
  25.               else
  26.                 first := mid + 1;
  27.             end;
  28.           if a[last] = z then
  29.             WriteLn(fout, 'YES')
  30.           else
  31.             WriteLn(fout, 'NO');
  32.         end;
  33.     end;
  34.  
  35.   Close(fin); Close(fout);
  36. end.

Объяснение кода листинга программы

  1. Объявляется массив a из 100000 элементов типа Longint.
  2. Объявляются переменные n и k типа Longint, а также переменные i, z, first, last, mid.
  3. Объявляются файлы fin и fout для ввода и вывода.
  4. Открывается файл input.txt для чтения и output.txt для записи.
  5. Считывается количество чисел n и k из файла input.txt.
  6. Для каждого числа от 1 до n считывается элемент a[i] из файла input.txt.
  7. Для каждого числа от 1 до k считывается число z из файла input.txt.
  8. Если число z меньше первого элемента массива a или больше последнего элемента массива a, выводится NO.
  9. Если число z находится в пределах массива a, происходит поиск бинарным методом.
  10. Пока переменные first и last не равны друг другу, вычисляется средний индекс mid и происходит сравнение числа z с элементом a[mid].
  11. Если число z меньше или равно элементу a[mid], переменной last присваивается значение mid.
  12. Если число z больше элемента a[mid], переменной first присваивается значение mid + 1.
  13. После завершения поиска, если элемент a[last] равен числу z, выводится YES, иначе выводится NO.
  14. Файлы input.txt и output.txt закрываются.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

15   голосов , оценка 4 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы