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

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

При поиске в упорядоченном массиве можно применить гораздо более быстрый метод поиска - бинарный. Суть его в следующем: В начале переменная Up указывает на самый маленький элемент массива (Up := 0), Down - на самый большой (Down := n, где n - верхний индекс массива), а Mid - на средний. Дальше, если искомое число равно Mid, то задача решена; если число меньше Mid, то нужный нам элемент лежит ниже среднего, и за новое значение Up принимается Mid + 1;и если нужное нам число меньше среднего элемента, значит, оно расположено выше среднего элемента, и Down := Mid - 1. Затем следует новая итерация цикла, и так повторяется до тех пор, пока не найдётся нужное число, или Up не станет больше Doun.

function SearchBin (Arr : array of Integer; v, n : Integer) : Integer;

var

Up, Down, Mid : Integer;

Found : Boolean;

begin

Up := 0; Down := n;

Found := False; Result := -1;

repeat

Mid := Trunc ((Down - Up) / 2) + Up;

if Arr [Mid] = v then

Found := True

else

if v < Arr [Mid] then

Down := Mid - 1

else

Up := Mid + 1;

until (Up > Down) or Found;

if Found then

Result := Mid;

end;

⇐ Предыдущая 1 23