Нужен пример бинарного поиска - Turbo Pascal

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

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

Бинарный поиск

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

textual
Листинг программы
function BinSearch(n: Integer; const a: array of Integer; Size: Integer): Integer;
var l, r, m: Integer;
begin
  l:=0; r:=Size-1;
  while l<=r do begin
    m:=l+(r-l) div 2;
    if a[m]>=n then r:=m-1 else l:=m+1;
  end;
  BinSearch:=l;
end;
 
const
  n=10;
var
  a: array [1..n] of Integer;
  i, k: Integer;
begin
  Randomize;
  for i:=1 to n do a[i]:=i*2;
  k:=Random(22);
  i:=BinSearch(k,a,n)+1;
  Write('Число ',k);
  if a[i]<>k then WriteLn(' не найдено.')
  else WriteLn(' найдено в позиции ',i,'.');
end.

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

  1. В функции BinSearch объявлены три переменные: l, r и m. Они представляют собой указатели на элементы массива a. Переменная l и r инициализируются как 0 и Size-1 соответственно, где Size - это размер массива.
  2. Затем в цикле while выполняются следующие действия:
    • m устанавливается как среднее значение между l и r. Это позволяет найти средний элемент массива при каждом проходе цикла.
    • Если значение a[m] больше или равно n, то это означает, что число n не найдено в массиве. В этом случае значение переменной r устанавливается равным m-1, что означает, что поиск продолжается в левой части массива.
    • Если значение a[m] меньше n, то это означает, что число n найдено в массиве. В этом случае значение переменной l устанавливается равным m+1, что означает, что поиск продолжается в правой части массива.
  3. После завершения цикла while значение переменной BinSearch устанавливается равным l, что является позицией, в которой найдено число n.
  4. В основной части программы объявляется переменная n, которая равна 10.
  5. Затем создается массив a, который содержит 10 чисел, каждое из которых удваивается.
  6. Выбирается случайное число k из диапазона от 1 до 22.
  7. Вызывается функция BinSearch с аргументами k, a и n. Результат поиска (позиция k в массиве) сохраняется в переменной i.
  8. Выводится сообщение о том, что число k найдено или не найдено в соответствующей позиции.
  9. Конец программы.

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

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