- Пример. Составьте программу двоичного поиска в отсортированном массиве.
Программный код (фрагмент) | Пояснение | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
Var status: boolean; | Окончание работы алгоритма | |||||||||
l, r: integer; | Левая и правая границы поиска | |||||||||
status := false; while ((l ＜= r) and (status ＜＞ true)) do begin mid := (l + r) div 2; if (mas[mid] = key) then status := true; | Проверка значения элемента, который находится в середине текущего массива | |||||||||
if (mas[mid] ＞ key) then r := mid - 1 else l := mid + 1 end; | Выбор левой/правой половины массива для дальнейшей работы алгоритма | |||||||||
Принцип бинарного поиска: | ||||||||||
1 | mas [0] | mas [1] | mas [2] | mas [3] | mas [4] | mas [5] | mas [6] | mas [7] | mas [8] | mas [9] |
left | mind | right | ||||||||
2 | mas [0] | mas [1] | mas [2] | mas [3] | ||||||
left | mind | right | ||||||||
3 | mas [2] | mas [3] | ||||||||
left/ mind | right | |||||||||