разделим на две части. При рассмотрении подмассива V
1
, соответственно, l1=5, r1=8,
mid=(5+8)/2. Исходный массив представляется в виде A[9]={6, 12, 18, 42} {44} { 56,
67} {94, 100}. (3)
Здесь могут быть следующие два случая: 1) исходя из точки деления, за
серединный элемент (назовём его неявным серединным элементом) разделённого
на две части подмассива V
1
={56, 67, 94, 100} выбирается первый элемент подмассива
V
3
={94, 100}, mid=7; V
1
[2]={94}= A[7]; 2) за серединный элемент выбирается
последний элемент подмассива V
4
={56, 67}, mid=6, V
1
[1]={67}= A[6]. В случае 1), так
как V
1
[2]=94> key=56, искомый элемент не содержится в подмассива V
3
={94, 100}.
Поэтому подмассив V
3
исключаем из рассмотрения. Искомый элемент будем искать в
подмассиве V
4
={56, 67}, находящемся слева от точки деления подмассива V
1
={56, 67,
94, 100} на две части. В случае 2), так как V
1
[1]= A[mid]= A[6]=67> key=56, искомый
элемент может содержаться до элемента V
1
[1]=A[6]=67 в подмассиве V
4
={56, 67}.
Искомый элемент будем искать в подмассиве V
4
={56, 67}, находящемся слева от
точки деления подмассива V
1
={56, 67, 94, 100} на две части. Далее, подмассив V
4
={56,
67} делим на две части. При рассмотрении подмассива V
4
, соответственно, l2=5, r2=6,
mid=(5+6)/2. Исходный массив можно представить в виде A[9]={6, 12, 18, 42} {44} {
56} {67} {94, 100}. (4)
161
Снова могут быть два случая: 1) исходя из точки деления, за серединный элемент
разделённого на две части подмассива V
4
={56, 67} выбирается первый элемент
V
5
[0]={67}= A[6] подмассива V
5
={67}, находящийся справа от точки деления, mid=6;
2) за серединный элемент выбирается последний элемент V
6
[0]={56}= A[5]
подмассива V
6
={56}, находящийся слева от точки деления, mid=5; В случае 1), так как
V
5
[0]= A[mid]= A[6]=67> key=56, то элемент V
5
[0]= 67 не является искомым
элементом и искомый элемент не содержится в подмассиве V
5
={67}, находящемся
справа от серединного элемента V
5
[0]= A[mid]= A[6]=67. Поэтому подмассив V
5
исключаем из рассмотрения. Искомый элемент будем искать в подмассиве V
6
={56},
находящемся слева от точки деления подмассива V
4
={56, 67} на две части. В случае
2) последний элемент V
6
[0]={56}= A[6] подмассива V
6
={56}, находящийся слева от
точки деления, mid=5 сравнивается с ключевым значением key=56. Так как
V
6
[0]=56= A[5]= key=56, то задача поиска элемента массива (1) со значением key=56
решена. Искомым элементом массива (1) со значением key=56 является элемент с
индексом mid=5, то есть элемент A[5]. Отметим, что если бы равенство V
6
[0]= key=56
не выполнилось, то это означало бы, что в исходном массиве (1) нет элемента со
заданным значением key=55, так как подмассив V
6
[0]={56} состоит из одного
единственного элемента и нет возможности продолжить процесс поиска путём
деления подмассива V
6
[0]={56} на две части.
Блок-схема бинарного алгоритма поиска элемента одномерного массива с
заданным значением приведена на рисунке 1. Блок 1 означает начало алгоритма,
блоки 2-3 – инициализацию массива A[9] путём ввода значений его элементов в
память компьютера с помощью клавиатуры. Упорядочение элементов
инициализированного массива с использованием стандартной функции sort(A, A+9)
описывает блок 4, где имя массива A, являющееся первым аргументом функции,
выполняет роль указателя, содержит адрес первого элемента массива A, этим самым
указывает на первый элемент массива A. Второй аргумент A+9 функции тоже
выполняет роль указателя, содержит адрес девятого элемента массива A, указывает
на девятый элемент массива A и этим самым обеспечивается выполнение операции
упорядочения с первого до девятый элементы массива A. Блок 5 описывает ввод
ключевого значения key, будет решаться задача поиска элемента массива A с
задаваемым значением key. При выполнении алгоритма поиска признаком того, что
в текущий момент времени искомый элемент найден или ещё не найден, будет
служить значение логической переменной sign (признак). Процесс поиска
начинается при значении false (ложь) переменной sign. В блоке 6 переменной sign
присваивается значение false, которое здесь и в дальнейшем означает, что искомый
элемент массива ещё не найден. Если в процессе поиска искомый элемент будет
найден, то переменной sign будет присвоено значение true (истина, правда) и это
значение будет служить признаком того, что искомый элемент найден, процесс
поиска надо прекратить. Значения l=0, r=9 (блок 7) являются значениями индексов
самого левого и самого правого элемента исходного массива. Алгоритм поиска
элемента массива с заданным значением имеет циклическую структуру и в каждом
цикле алгоритма поиска проверяется выполнение или невыполнение следующих
двух условий (блок 8): sign # true, l<=r. (5). Если одновременно выполняются оба
условия (5), то это означает, что искомый элемент ещё не найден (sign # true), а
массив или подмассив, в котором собираемся искать искомый элемент, не пустой,
содержит по меньшей мере один элемент (l<=r). Если lболее одного элемента, при l=r подмассив содержит один элемент. В обоих случаях
процесс поиска элемента можно продолжить (блоки 9-14).
|
