Выше мы продемонстрировали использование метода линейного (последовательного) поиска, суть которого заключается в последовательном просмотре всего списка элементов массива и сравнении значения очередного элемента с заданным для поиска. Этот метод поиска вполне эффективен на неупорядоченных массивах данных, а на предварительно отсортированных массивах значительно эффективнее выполнять поиск другими методами. Например, метод линейного поиска практически бесполезен при поиске информации в массивах большого размера, так как занимает много времени.
Одним из эффективных методов поиска в больших отсортированных массивах является бинарный поиск, или поиск методом деления пополам. В основе этого метода лежит идея целенаправленных последовательных догадок о предполагаемом местоположении искомого элемента. Такой метод можно проиллюстрировать на примере шуточного совета, как поймать в Африке льва: «Для начала разделим Африку пополам. Ясно, что лев находится только в одной половине. Та половина, в которой находится лев, снова делится пополам, и т. д. Площадь Африки приблизительно 30 млн км2. Следовательно, после примерно 45 делений;мы получим площадку, не превышающую 1 м2. Теперь на такой площадке льва поймать нетрудно».
Аналогично выполняется бинарный поиск элемента в упорядоченном массиве. Вместо просмотра подряд всех элементов массива разделим его пополам. Так как массив отсортирован, то, сравнивая искомый элемент со значением среднего элемента массива, мы в состоянии сделать вывод о том, может ли элемент с таким значением присутствовать в массиве и в какой половине он находится, т. е. определить область дальнейшего поиска. Затем делится пополам та часть массива, в которой находится элемент, и так до тех пор, пока рассматриваемая часть массива получится состоящей из одного элемента.
Упражнение 2.Создадим программу, выполняющую бинарный поиск заданного элемента в отсортированном массиве целых чисел, элементы которого имеют значения: 20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 5, 3, 3, 2, 1.
Введем в разделе описания констант размер массива Count = 20 и опишем массив целых чисел:
В разделе описания переменных опишем следующие переменные:
N — для хранения значения искомого элемента;
I — для указания очередного элемента массива;
First — указание индекса элемента, являющегося левой границей рассматриваемой части массива;
Last — указание индекса элемента, являющегося правой границей рассматриваемой части массива;
Found — логическая переменная, в которую будет записываться результат поиска;
А — переменная, значение которой будет равно числу перестановок элементов,
В начале программы реализуем вывод исходного массива на экран, затем вывод запроса искомого элемента, после чего считывание его значения в переменную N.
Перед началом поиска обнулим счетчик повторений А, установим левую и правую границы рассматриваемой части массива, а переменной Found присвоим значение False — элемент пока не найден.
Текст программы будет выглядеть следующим образом: program Find_Bin;
Write ('Введите значение элемента массива для поиска >');
Readln(N);
А:=0;
First := 1;
Last := Count;
Found:=False; {Элемент, не найден} repeat {Повторять поиск}
I := (First + Last) div 2; {Разделить на две части}
if M[I] = N then Found:=True
else
begin
if M[I] > N then first := I+1 {Искать элемент в правой части} else Last := I-1; {Искать злемект в левой части} end;
А:=А+1; {Увеличить счетчик числа итераций}
until (Found) or (First>Last); {Завершить, если найдется искомый элемент или будет просмотрен весь массив}
if Found then Writeln('Искомый элемент ' ,N, ‘ в массиве занимает’ ,I, ' - ю позицию ‘)
else
Writeln (‘B массиве нет искомого элемента ', N);
Writeln (‘Поиск выполнен за ' ,А, ' итераций ');
end.
Обратите внимание на то, что бинарный поиск в сортированных массивах выполняется за небольшое число итераций!
Упражнение 3.Создадим программу, формирующую двумерный массив случайных чисел и вычисляющую значение среднего арифметического его элементов, больших, чем 20. Решение задачи сводится к последовательному перебору всех элемёнтов-массива с вычислением суммы тех элементов, значение которых больше 20, а по окончании их суммирования производится вычисление частного полученной суммы и количества элементов массива, удовлетворяющих условию суммирования.
В разделе описания программы опишем квадратный двумерный массив, указав в разделе описания констант количество строк Strok =15 и количество столбцов Stolb =15, а в разделе описания переменных — массив целых чисел:
D : array (L ..Strok, J..Stolb] of integer;
Для указания положения элемента в массиве введем переменные:
I — номер строки, в которой расположен элемент;
J—номер столбца, в котором расположен элемент.
Для подсчета количества элементов массива, больших 20, введем целую переменную К, а для подсчета их суммы, а затем и значения среднего арифметического введем вещественную переменную S. Для заполнения массива случайными целыми числами применим функцию Random и поэтому в начале описания поместим подключение стандартного модуля Crt, в котором она содержится.
Полный текст программы решения задачи будет выглядеть таким образом:
program Sum_Mas_2;
uses Crt;
const
Strok=15; '
Stolb=15;
var
D: array[I..Strok, J..Stolb] of Integer;
I, J, К : integer;
S : real;
begin
Randomize; {Генерация массива случайных чисел} for I:= 1 to Strok do
for J:= 1 to Stolb do
D[I, J]:=Random(99);
S:= 0;
K:= 0;
for I:= 1 to Strok do {Вычисление сунмы элементов массива>20} begin
for J:= 1 to Stolb do {Просмотр всех элементов в 1-й строке} begin
Write (D[I, J]:2, ' '):
if D[I, J] >20 then {Если найден элемент D[I.J]>20} begin
