- Пример. Составьте программу двоичного поиска в отсортированном массиве.
Программный код | Пояснение | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
bool status = false; | Окончание работы алгоритма | |||||||||
int l, r; | Левая/правая границы поиска | |||||||||
int mid; while ((l ＜= r) (status != true)) { mid = (l + r) / 2; if (mas[mid] == key) status = true; | Проверка значения элемента, который находится в середине текущего массива | |||||||||
if (mas[mid] ＞ key) r = mid - 1; else l = mid + 1; } | Выбор левой/правой половины массива для дальнейшей работы алгоритма | |||||||||
Принцип бинарного поиска: | ||||||||||
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 | |||||||||