ПОШУК, СОРТУВАННЯ ТА ПОНЯТТЯ СКЛАДНОСТІ У ПРОГРАМУВАННІ

Очевидно, що кількість елементарних дій при виконанні функції srcseq прямо пропорційна кількості порівнянь A[i]<>key. В найгіршому випадку з ключем порівнюються всі елементи масиву. Звідси максимальна кількість дій та найбільший час виконання функції прямо (лінійно) пропорційні n, і найбільший час пошуку t1 є лінійною функцією від кількості елементів масиву. Описаний спосіб пошуку називається лінійним. Лінійну залежність часу від кількості елементів, тобто довжини n, будемо позначати символом "O": t1 = O(n).

1.2. Дихотомічний пошук

Тепер опишемо так званий дихотомічний пошук у "нормальному словнику". Ми розкриваємо словник приблизно в його середині. Якщо слово повинно бути в словнику далі, то шукати треба лише в другій половині словника. Його середина стає для нас початком, і ми розкриваємо його на середині другої половини. Аналогічно, коли слово повинно бути в першій половині, ми залишаємо для пошуків лише її. Отже, кожне заглядання в словник поділяє "простір пошуку" на дві половини й зменшує його приблизно вдвічі. Звідси й назва, оскільки дихотомія – це поділ на дві половини. Такий пошук ще називають двійковим, або бінарним.

Нехай значення елементів масиву упорядковані за зростанням, тобто A[1] A[2] …  A[n] (кажуть, масив відсортований). Опишемо дихотомічний пошук такою функцією:

function srcbin ( var A : ArT; n : Indx; key : T) : integer;

var i, hb, lb : integer;

begin

lb := 1; hb := n;

i := (lb + hb) div 2;

while (lb < hb) do

begin

if A[i] = key then break else

if A[i] > key

then hb := i - 1 { key може бути лише ліворуч від A[i] }

else lb := i + 1; { key може бути лише праворуч від A[i] }

i := (lb + hb) div 2

end;

{ lb >= hb або A[i] = key }

if (i=0) or (i=n+1) then srcbin := 0 else

if A[i] = key then srcbin := i else srcbin := 0

end