Поиск минимального (максимального) элемента.

Алгоритм поиска минимального (максимального) элемента массива следующий: сначала делается предположение, что первый элемент массива является минимальным (максимальным), затем остальные элементы массива последовательно сравниваются с этим элементом. Если во время очередной проверки обнаруживается, что проверяемый элемент меньше (больше) принятого за минимальный (максимальный), то этот элемент становится минимальным (максимальным) и продолжается проверка оставшихся элементов.
1.1 Найти минимальное значение элементов последовательности (все элементы различные).
Идея: поиск проводим путем сравнения всех элементов с эталоном переменной, которой заранее присваивается значение какого-нибудь элемента. Если сравнивается элемент меньше эталона, то надо изменить эталон, затем продолжить процесс для других элементов последовательности. В итоге эталон будет равен минимальному значению элементов последовательности.

PROCEDURE POISK_1 (x: massiv; VAR min: element);
VAR i: integer;
begin
¦ min: = x[1];
¦ FOR i: =2 to n do begin
¦ if x[i]< min then ¦
¦ min: = x[i] ¦
¦ end;
¦
end;

1.2. Найти номер минимального элемента последовательности (все элементы различные).
Идея: надо найти минимальный элемент по алгоритму задачи 1.1, добавив в него запоминание номера, параллельно с изменением эталона меняется запоминаемый номер. В итоге алгоритма получается номер минимального элемента последовательности. Следует учесть, что возможен случай, когда минимальным является первый рассматриваемый элемент.

PROCEDURE MIN_NOM (x: massiv; VAR nomer: integer);
VAR i: integer;
BEGIN
¦ min: = x[1]; nomer: = 1;
¦ FOR i: = 2 to n do
¦ if x[i]< min then begin
¦ min: = x[i]; nomer: = i; ¦
¦ end;
¦
END;

1.3. Найти минимальный элемент и его номер в последовательности с совпадающими элементами.
При решении этой задачи необходимо оговорить, какой именно, первый или последний, элемент считать искомым.

PROCEDURE POISK_2 (x: massiv; VAR min: element; nomer: integer);
var i: integer;
begin
¦ min: = x[1]; nomer: = 1;
¦ for i: = 2 to n do
¦ if x[i]< = min then begin min: = x[i]; nomer: =i; end;
¦
end;

Если поставлена задача отыскания первого по порядку следования минимального элемента и его номера, то используется условие: 'эталон' > 'текущее'.
Если ищется последний по порядку минимальный элемент и его номер, то надо использовать такое условие: 'эталон' > = 'текущее'.

Поиск элемента с заданным значением.
Для организации поиска в массиве могут быть использованы различные алгоритмы. Наиболее простой — это алгоритм простого перебора. Поиск осуществляется последовательным сравнением элементов массива с образцом до тех пор, пока не будет найден элемент, равный образцу, или не будут проверены все элементы. Алгоритм простого перебора применяется, если элементы массива не упорядочены.

Требуется найти номер элемента с заданным значением (все элементы различные). Пусть задана последовательность {Xi}, i=1,..., N и переменная Р, которая называется поисковой (эталон). Известно, что в {Xi} все элементы имеют различные значения. Требуется определить номер элемента, значение которого равно значению Р. Самый поверхностный анализ выявляет особенность: в последовательности может не быть элемента со значением Р. Такую ситуацию надо рассмотреть при конструировании алгоритма.

2.1. Поиск в неупорядоченной последовательности.
Для поиска элемента в неупорядоченной последовательности используется алгоритм простого перебора.
Идея: поиск осуществляется последовательным сравнением элементов массива с образцом до тех пор, пока не будет найден элемент, равный образцу, или не будут проверены все элементы. Когда обнаруживается искомый элемент, запоминается его номер. Необходимо учесть случай, когда искомого значения нет.

PROCEDURE NEUPPOS (var x: massiv; P: element);
var i, K: integer;
begin
¦ K: = 0
¦ for i: =1 to n do
¦ if x[i]= P then K: = i;
¦ if K=0 then write ('нет элемента')
¦ else write ('номер =', K);
end;

2.2. Поиск в упорядоченной последовательности.
На практике довольно часто производится поиск в массиве, элементы которого упорядочены по некоторому критерию. Например, массив фамилий, как правило, упорядочен по алфавиту, массив данных о погоде — по датам наблюдений. В случае, если массив упорядочен, то применяют другие, более эффективные по сравнению с методом простого перебора алгоритмы, например – метод бинарного поиска.
Идея: в процессе поиска границы промежутка сдвигаются друг к другу, причем после каждого сравнения изменяется только одна граница: либо верхняя, либо нижняя. Алгоритм, использующий последовательное уменьшение промежутка в 2 раза, также называется дихотомия (деление пополам). Обозначим:
No - номер наименьшего элемента последовательности;
Nk - номер наибольшего элемента последовательности;
i – средний (по номеру) элемент в массиве.
Алгоритм бинарного поиска реализуется следующим образом:
1. Сначала образец сравнивается со средним (по номеру) элементом массива.

· Если образец равен среднему элементу, то задача решена.

· Если образец больше среднего элемента, то это значит, что искомый элемент расположен правее среднего элемента (между элементами с номерами i+1 и Nk), и за новое значение No принимается i+1, а значение Nk не меняется.

· Если образец меньше среднего элемента, то это значит, что искомый элемент расположен левее среднего элемента (между элементами с номерами No и i-1), и за новое значение Nk принимается i-1, а значение No не меняется.

2. После того как определена часть массива, в которой может находиться искомый элемент, по формуле (Nk + N0) div 2 вычисляется новое значение i и поиск продолжается.

Основой алгоритма является цикл, выполняемый неопределенное количество раз. В этом цикле интервал номеров делится пополам, получается номер под названием INDEX. Элемент с этим номером сравнивается с поисковой переменной Р. В зависимости от результата сравнения: перевычисляется No или Nk. Это повторяется до тех пор, не обнаружится элемент или No и Nk не совпадут, затем делается проверка X[No]=Р и по ее исходу формируется результат.

PROCEDURE DICHOTOM (VAR x: massiv; P: element;
VAR INDEX: integer)
VAR i, No, Nk: integer;
BEGIN
¦ No: =1; Nk: =n; INDEX: =0;
¦ REPEAT
¦ i: =(No + Nk) div 2
¦ if x[i]= P then INDEX: = i
¦ else
¦ if x[i]> P then Nk: = i-1
¦ else No: =i+1
¦ UNTIL (INDEX > 0) or (No > Nk)
END;

Последовательный поиск. " Начать с начала и продолжать, пока не будет найден искомый ключ; затем оста­новиться". Эта последовательная процедура представляет собой очевидный путь поиска и может служить отличной отправной точкой для рассмотрения множества алгоритмов поиска, поскольку они основаны на последовательной процедуре.
Ниже представлена более точная формулировка алгоритма.
Алгоритм S (Последовательный поиск (Sequential search)). Дана таблица записей R1, R2,..., Rn с ключами К1, К2,..., Kn соответственно. Алгоритм предназначен для поиска записи с заданным ключом К. Предполагается, что N > 1.
S1. [Инициализация.] Установить i: = 1.
S2. [Сравнение.] Если К = Кi, алгоритм заканчивается успешно.
S3. [Продвижение.] Увеличить i на 1.
S4. [Конец массива] Если i < N, перейти к шагу S2. В противном случае алгоритм заканчивается неудачно.

Двоичный поиск. Последовательный поиск вы­полняется очень быстро для небольших объёмов информации. Большие – намного быст­рее обрабатывает алгоритм двоичного поиска. Алгоритм двоичного поиска сравнивает элемент в середине списка с искомым. Если искомый элемент меньше, алгоритм продолжает перебирать первую половину списка, если же он больше, чем найденный элемент, поиск продолжается во второй половине списка. На рисунке процесс поиска элемента со значением 44 изображен графически.

Интерполяционный поиск. Двоичный поиск оптимизирует поиск полным перебором, так как исключает большие части списка, не проверяя значения пропускаемых элементов. Если изве­стно, что значения распределены достаточно равномерно, то можно на каждом шаге исключить еще большее количество элементов, используя интерполяционный поиск.
Интерполяция - это процесс предсказания неизвестных значений на основе имеющихся. В данном случае вы используете индексы известных значений в спис­ке, чтобы определить, какой индекс должно иметь искомое значение. Предполо­жим, что вы имеете такой же список. Этот список содержит 20 элементов со значениями от 1 до 70. Допустим, что вы хотите найти в этом списке элемент со значением 44. Значение 44 составляет 64% размера диапазона от 1 до 70. Если считать, что значения элементов распределены равномерно, то искомый элемент, предположительно, будет находиться в позиции, составляющей 64% от размера списка - то есть в позиции с индексом 13.
Если найденная алгоритмом позиция неверна, то он сравнивает искомое зна­чение со значением в выбранной позиции. Если искомое значение меньше, алго­ритм продолжает искать элемент в первой части списка, если больше, то поиск продолжается во второй части списка. На рисунке графически представлен про­цесс интерполяционного поиска.

Program Sort;

PROCEDURE MIN_NOM (x: Array of integer; n: integer);

VAR i, nomer, min: integer;

BEGIN

min: = x[1];

nomer: = 1;

FOR i: = 2 to n do

if x[i]< min then begin

min: = x[i]; nomer: = i;

end;

Writeln (min);

Write (nomer);

END;

Const

Nmax = 100;

Var

X: Array [1..Nmax] Of integer;

n, i: Integer;

Begin

Writeln('‚ўҐ¤ЁвҐ Є®«ЁзҐбвў® зЁбҐ«');

Readln(n);

Writeln('‚ўҐ¤ЁвҐ ббЁў зЁбҐ«');

For i: = 1 To n Do Read (X[i]);

MIN_NOM(X, n);

readln(n);

End.