Для каждого из 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.

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

  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
Похожие ответы