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