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