Дихотомический поиск (поиск элемента в упорядоченном массиве)Алгоритм дихотомического поиска достаточно прост. Делим массив пополам и определяем, в какой из частей может находиться искомый элемент. Поскольку массив упорядочен то, сравнивая искомый элемент со средним элементом массива, легко определить интересующую нас половину. Затем выбранную половину опять делим пополам и определяем, в какой половине находится искомый элемент. Этот процесс продолжаем до тех пор, пока не будет найден искомый элемент, либо левая граница нового отрезка не станет больше правой. В последнем случае можно сделать вывод о том, что искомого элемента в массиве нет. 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
|
