Бинарный поиск чисел в массиве - Pascal
Формулировка задачи:
Привет!
Никак не могу доработать программу: выводит только ответ для последнего значения второго массива.
Заранее спасибо.
Листинг программы
- uses sysutils;
- var x,y:array[1..1000] of longint;
- m, n, a, i ,j,temp, left, right, middle:integer;
- flag:boolean;
- kek: byte;
- begin
- for kek:=1 to 20 do writeln(' ');
- readln(n);
- readln(m);
- for i:=1 to n do begin
- read(x[i]);
- end;
- for j:=1 to m do begin
- read(y[j]);
- end;
- left:=1;
- right:= n;
- flag:=false;
- while (left <= right) and not flag do
- begin
- middle:=(left+right) div 2;
- if y[j]<x[middle] then right:=middle-1
- else if y[j]>x[middle] then left:=middle+1
- else flag:=true;
- end;
- if not flag then writeln('-1')
- else writeln(y[j]);
- end.
Решение задачи: «Бинарный поиск чисел в массиве»
textual
Листинг программы
- var
- a: array [0..99999] of Integer;
- m, n, i, b, lt, rt, md: Integer;
- begin
- Read(m,n);
- for i:=0 to m-1 do Read(a[i]);
- for i:=1 to n do begin
- Read(b); lt:=0; rt:=m;
- while lt<rt do begin
- md:=lt+(rt-lt) div 2;
- if a[md]<b then lt:=md+1 else rt:=md;
- end;
- if (lt<m) and (a[lt]=b) then Write(' ',lt+1) else Write(' ',-1);
- end; WriteLn;
- end.
Объяснение кода листинга программы
- Объявляется массив a размером от 0 до 99999
- Объявляются переменные
m
,n
,i
,b
,lt
,rt
,md
типа Integer - Считывается значение переменных
m
иn
с клавиатуры - В цикле от 0 до
m-1
считываются значения элементов массиваa
с клавиатуры - В цикле от 1 до
n
делается следующее:- Считывается значение переменной
b
с клавиатуры - Устанавливается значение переменной
lt
в 0 иrt
вm
- Запускается цикл, который выполнится до тех пор, пока
lt
меньшеrt
- Внутри цикла вычисляется значение
md
(середина), а затем проверяется условие: если a[md] меньше b, тоlt
присваивается значениеmd+1
, в противном случаеrt
присваивается значениеmd
- После завершения цикла, если
lt
меньшеm
и значениеa[lt]
равноb
, то выводится номер позицииlt+1
, иначе выводится-1
- Считывается значение переменной
- После завершения внешнего цикла выводится результат перехода на новую строку
Данный код реализует бинарный поиск чисел в массиве
a
и выводит номер позиции найденного элемента или -1, если элемент не найден.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д