Решение
Разберемся в блок-схеме программы. Разметим элементы блок-схемы так, чтобы можно было ссылаться на них (см. рис.).
Рис. Размеченная блок-схема
Поскольку массив A имеет N элементов, то можно предположить, что L и H в (1) обозначают начальный и конечный индексы элементов массива, т.е. A[L] = A[0], A[H]=A[N-1]. Видно, что блоки (2)-(7) образуют цикл, в котором используется индексирующая элементы массива переменная i. В (2) эта переменная принимает значение середины в диапазоне (L,H), и элемент массива A[i] проверяется на равенство с X. Если равенство A[i]=X истинно, то результат программы достигается. Естественно утверждать, что в массиве A[] ищется число X.
В (4)-(7) производится изменение диапазона индексов элементов массива A[], среди которых ищется число X, если оно еще не найдено. Сравнение (4) позволяет говорить о том, что A[] упорядочен по возрастанию элементов в нем.
Итак, на блок-схеме изображена программа поиска числа X в упорядоченном по возрастанию элементов массиве A[]. Алгоритм этого поиска называют «делением пополам».
В разобранной программе производится просмотр и сравнение не всего массива A[], а некоторой его части, при этом изначально исключается половина массива. В результате максимальное число сравнений равно, log2 N, округленному до ближайшего целого.
