Дихотомический поиск (поиск элемента в упорядоченном массиве)

Алгоритм дихотомического поиска достаточно прост. Делим массив пополам и определяем, в какой из частей может находиться искомый элемент. Поскольку массив упорядочен то, сравнивая искомый элемент со средним элементом массива, легко определить интересующую нас половину. Затем выбранную половину опять делим пополам и определяем, в какой половине находится искомый элемент. Этот процесс продолжаем до тех пор, пока не будет найден искомый элемент, либо левая граница нового отрезка не станет больше правой. В последнем случае можно сделать вывод о том, что искомого элемента в массиве нет.

const n = 20 ‘количество элементов в массиве

dim a(1 to n) ‘исходный массив

defint i, x, k, m,f

defint left, right, mid ‘левая, правая граница и середина отрезкa

input “задайте искомый элемент”;k ‘ Основной блок программы

for i = 1 to n

input a (i)

‘упорядочивание массива по возрастанию

for i = 1 to n – 1

m = i

for j = i + 1 to n

if a(j) < a(m) then m =j

next

x = a(i): a(i) = a(m): a(m) = x

next

‘поиск элемента

f = 0 ‘элемент не найден

left = 1: right = n

DO ‘поиск элемента в части массива от элемента [left] до элемента [rigth]

mid = (left + right) \ 2

if k < a(mid) then right = mid – 1 ‘элемент в левой части

else if k > a(mid) then left = mid + 1 ‘элемент в правой части

else f = 1 ‘нашли

LOOP until f<>0 or (left > rigth)

if f=1 then print “элемент с номером”; mid; “‘совпадает с исковым”; k

else print ”‘не нашли”

End