Поиск номера элемента последовательности с заданным значением

Рассмотрим задачу D. Пусть задана последовательность {X_i} = Х₁, Х₂, ..., X_N, где i изменяется от 1 до N. По условию в последовательности {X_i} все элементы имеют разные значения. Необходимо определить номер элемента, значение которого равно значению некоторой заданной переменной Р. Причем в заданной последовательности может не оказаться элемента со значением Р. Первая ситуация - упорядоченная последовательность.

Основной алгоритм поиска имеет следующий вид:

a. Сравнить очередной элемент с переменной Р.

b. Перейти к следующему элементу.

c. Если не все элементы просмотрены, то повторить с п. а.

Алгоритм должен однозначно реагировать на ситуацию, если искомого значения в последовательности нет. Введем переменную k с начальным значением, равным 0. Результат k - номер найденного элемента.
Если элемент со значением Р не найден, то результат k остается нулевым (рис. 1.13). Если последовательность упорядочена, т. е. значения элементов последовательности возрастают или убывают с увеличением порядковых номеров (индексов) элементов, то к ней можно применить другой алгоритм поиска. В процессе поиска можно сдвинуть друг к другу границы промежутка, в котором после каждого сравнения сдвигается либо верхняя, либо нижняя граница. Алгоритм, в котором последовательно уменьшается промежуток исследуемых данных в два раза, называется алгоритмом дихотомии - деление отрезка пополам.
Пусть значение наименьшего элемента исходной последовательности равно А, а значение наибольшего элемента - В. Если разделить рассматриваемый интервал [А, В] пополам, то получится некоторое значение С. Сравнить С с заданным значением Р. Повторять эти действия до тех пор, пока А и В не совпадут. Проверить условие Х[А] = Р. По результатам проверки должен быть сформирован результат.

Рис. 1.13. Схема алгоритма поиска заданного элемента

Словесный алгоритм поиска имеет следующий вид:

a. Вычислить С.

b. Сравнить Х[С] с переменной Р.

c. Определить А и В.

d. Если А и В не совпадают, то повторить с п. а.

e. Проверить совпадение выделенного значения с поисковой Р.

Рис. 1.14. Схема алгоритма дихотомического поиска

Необходимо задать начальные значения А и В. Схема алгоритма дихотомического поиска в упорядоченном массиве представлена на рис. 1.14.

Сортировка
Сортировка стала важной частью вычислительной математики, так как она отнимает значительную часть времени работы компьютера (25%). Сортировка относится к алгоритмам обработки таблиц (массивов) любого типа.
Смысл любой сортировки заключается в перестановке элементов таблицы в определенном заданном порядке. Отсортировать числовую таблицу - это значит переставить элементы в ней так, чтобы они расположились в порядке убывания (возрастания) значений с возрастанием нового номера элемента:

Номер элемента	1	2	3	4	5
Исходный числовой массив	7	12	1	49	3
Упорядочение по возрастанию	1	3	7	12	49
Упорядочение по убыванию	49	12	7	3	1

Сортировка символьной (или текстовой) информации заключается в упорядочении значений (текстовых строк) по алфавиту:

Номер элемента	1	2	3	4	5
Исходный символьный массив	мул	кот	як	лев	вол
Упорядочение по алфавиту	вол	кот	лев	мул	як

Метод сортировки является устойчивым, если относительный порядок элементов с равными значениями не меняется после упорядочения. Сортировку можно рассматривать и как самостоятельную задачу (например, для получения упорядоченного по алфавиту списка сотрудников какого-либо учреждения), и как вспомогательную - для облегчения последующего поиска элементов в упорядоченной таблице. Анализ известных алгоритмов сортировки очень полезен, так как в них используется практически все универсальные приемы конструирования алгоритмов. В пособии представлены алгоритмы упорядочения последовательности A₁,A , ..., A_N, по возрастанию. Переход к упорядочению по убыванию аналогичен.