Реализуйте алгоритм бинарного поиска - Pascal

Узнай цену своей работы

Формулировка задачи:

Помогите пожалуйста перевести программу с С++ на Паскаль, заранее спасибо
#include <algorithm>
#include <iostream>
#include <cstdio>
 
using namespace std;
 
int a[100111];
 
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
 
    for (int i = 0; i < k; i++)
    {
        int x;
        scanf("%d", &x);
 
        int l = 0;
        int r = n - 1;
        while (l < r)
        {
            int d = (l + r) / 2;
            if (a[d] < x) l = d + 1; else r = d;
        }
 
        if (a[l] == x) printf("YES\n"); else printf("NO\n");
    }
}
Задание: Реализуйте алгоритм бинарного поиска.

Входные данные

В первой строке входных данных содержатся натуральные числа 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

Решение задачи: «Реализуйте алгоритм бинарного поиска»

textual
Листинг программы
const mn=10000;
var
  a: array [0..mn-1] of Longint;
  n, k, x, i, l, r, d: Longint;
begin
  ReadLn(n, k);
  for i:=0 to n-1 do Read(a[i]); ReadLn;
  for i:=0 to k-1 do begin
    Read(x);
    l:=0; r:=n-1;
    while l<r do begin
     d:=l+(r-l) div 2;
     if a[d]<x then l:=d+1 else r:=d;
    end;
    if a[l]=x then WriteLn('YES') else WriteLn('NO');
  end;
end.

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

  1. Объявление константы mn и переменных a, n, k, x, i, l, r, d типа Longint.
  2. Считывание значений переменных n и k с помощью ReadLn.
  3. Чтение элементов массива a через цикл for.
  4. Чтение значения переменной x.
  5. Установка начальных значений переменных l и r на 0 и n-1 соответственно.
  6. Пока l < r, выполняется цикл, в котором значение переменной d устанавливается равным l плюс r-l, деленное на 2.
  7. Если значение элемента массива a[d] меньше x, то l увеличивается на 1, иначе r становится равным d.
  8. Если значение элемента массива a[l] равно x, то выводится 'YES', иначе выводится 'NO'.
  9. Цикл повторяется k раз.

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


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

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

5   голосов , оценка 4 из 5
Похожие ответы