Бинарный поиск — проект на Delphi

DP.21 · Алгоритмы

Задача

Найти индекс числа в отсортированном массиве.

Алгоритм

Диапазон поиска делится пополам: если середина меньше искомого — идём вправо, иначе влево.

Исходный код

program BinarnyyPoisk;
{$mode delphi}{$apptype console}
var a: array[0..9] of Integer = (1, 3, 5, 7, 9, 11, 13, 15, 17, 19);
function Search(x: Integer): Integer;
var lo, hi, mid: Integer;
begin
  lo := 0; hi := High(a);
  while lo <= hi do begin
    mid := (lo + hi) div 2;
    if a[mid] = x then Exit(mid)
    else if a[mid] < x then lo := mid + 1
    else hi := mid - 1;
  end;
  Result := -1;
end;
var x, idx: Integer;
begin
  Write('Искать число: '); ReadLn(x);
  idx := Search(x);
  if idx >= 0 then WriteLn('Найдено, индекс ', idx) else WriteLn('Не найдено');
  ReadLn;
end.

Пояснения

Работает только на отсортированных данных, но даёт O(log n) вместо O(n).