Рис. 1. Графическое описание бинарного алгоритма поиска элемента одномерного
массива с заданным значением key
Отметим, что при первом обращении к блоку 8 оба условия (5), а вместе с ними и
условие (sign # true) && ( l<=r) (6) в блоке 8 выполняются, переходим к блоку 9 и
вычисляем индекс mid явного или неявного серединного элемента. В блоке 10
проверяется, равно ли значение серединного элемента с индексом mid ключевому
163
значению key. Если получаем ответ «да», то рассматриваемый серединный элемент
является искомым элементом массива со значением key, переменной sign
присваивается значение true (блоке 11) и возвращаемся к блоку 8. Если же значение
серединного элемента не равно ключевому значению key, то это означает, что
рассматриваемый серединный элемент не является искомым элементом массива со
значением key, искомый элемент ещё не найден, процесс поиска необходимо
продолжить. Переходим к блоку 12. Поиск искомого элемента продолжим в одном из
подмассивов, на которые подразделяется исходный массив серединным элементом.
Для определения подмассива, в котором необходимо продолжить процесс поиска,
проверяется выполнение, например, условие A[mid] > key, то есть больше ли
значение серединного элемента значения искомого элемента. Если получаем ответ
«да», то это означает, что искомый элемент может быть в левом подмассиве и будем
искать его в левом подмассиве, а правый подмассив исключаем из рассмотрения.
При этом значение параметра l, как значение индекса элемента, являющегося левой
границей подмассива, в котором будет продолжен процесс поиска искомого
элемента, остаётся прежним, а значение r, как значение индекса элемента,
являющегося правой границей этого подмассива, уменьшается на 1 (блок 13). Если
условие A[mid] > key в блоке 12 не выполняется, то A[mid]может быть в правом подмассиве и будем искать его в правом подмассиве, а левый
подмассив исключаем из рассмотрения. При этом значение параметра r , как
значение индекса элемента, являющегося правой границей подмассива, в котором
будет продолжен процесс поиска искомого элемента, остаётся прежним, а значение l,
как значение индекса элемента, являющегося левой границей нового подмассива,
увеличивается на 1 (блок 14). В обоих случаях, с новым значением параметра l или r,
переходим к блоку 8 для продолжения процесса поиска искомого элемента в
определённом подмассиве.
До сих пор рассматривался случай, когда оба логических выражения в (5), а
вместе с ними и логическое выражение (6) имеют значения true. Теперь
проанализируем случай, когда логическое выражение (6) имеет значение false.
Согласно логической арифметике, это может быть в следующих трёх случаях: 1)
условие sign # true не выполняется, а условие l<=r выполняется; 2) условие sign #
true выполняется, а условие l<=r не выполняется; 3) оба условие sign # true и l<=r не
выполняется. В первом случае sign=true, это означает, что прежнее, исходное
значение false переменной sign изменилось на true, а такое изменение значения
происходит, если в процессе поиска искомый элемент массива со значением key
найден. Переходим к блоку 15, в этом случае блок 15 может показаться лишним, но
он служит и для другого случая. Выдаётся на печать значение индекса искомого
элемента массива со значением key, которым является значение параметра mid
(блок 16). Найденный искомый элемент может быть одним из нескольких
элементов рассматриваемого подмассива (l(l=r). Поставленная задача решена положительно, алгоритм её решения завершается
(блок 18). Во втором случае sign # true, то есть sign= false, прежнее, исходное
значение false переменной sign не изменилось на true, а это имеет место, когда в
процессе поиска элемент массива со значением key не найден. Ясность в вопросе
вносит невыполнение условия l<=r, то есть невыполнение условий lиз которых означает, что последний рассмотренный подмассив состоял из одного
элемента, этот элемент не оказался искомым элементом. Ясно, что последний
рассмотренный подмассив, состоящий из одного элемента, невозможно разбить на
подмассивы в целях продолжения процесса поиска искомого элемента. Таким
образом, на данный момент времени искомый элемент не найден, и возможности
создания подмассивов в целях продолжения процесса поиска искомого элемента
164
исчерпаны. Следовательно, в исходном массиве нет элемента со значением key. Блок
17 выдаёт информацию об этом и процесс поиска прекращается (блок 18). Ниже
приведена часть результатов вычислительных экспериментов на компьютере по
реализации бинарного алгоритма поиска применительно к массиву (1).
Введите ключ: key=56. В массиве есть элемент со значением 56, его индекс равен
5.
Введите ключ: key=79. В массиве нет элемента со значением 79.
|
