Урок 12
§8. Структурированные типы данных. Массивы

8.2. Задачи поиска элемента с заданными свойствами

Очень часто в реальной жизни нам приходится сталкиваться с задачей поиска информации в большом массиве данных. Например, поиск нужного слова в словаре, поиск времени отправления нужного поезда в расписании, поиск нужного товара в интернет- магазине и т. д.

В программировании поиск — одна из наиболее часто встречающихся задач невычислительного характера.

В алгоритмах поиска существует два возможных варианта окончания их работы: поиск может оказаться удачным — заданный элемент найден в массиве и определено его месторасположение, либо поиск может оказаться неудачным — необходимого элемента в данном объёме информации нет.

Рассмотрим несколько типовых задач поиска, первое знакомство с которыми у вас состоялось ещё в основной школе.

Пример 3. Последовательный поиск в неупорядоченном массиве.

Имеется массив а[1..n]; требуется найти элемент массива, равный р.

Алгоритм последовательного поиска в неупорядоченном массиве может быть следующим.

1. Установить i = 1.
2. Если a[i] = р, алгоритм завершил работу успешно.
3. Увеличить i на 1.
4. Если i ≤ n, то перейти к шагу 2. В противном случае алгоритм завершил работу безуспешно.

Возможная программа, реализующая этот алгоритм на языке Pascal, имеет вид:

Внимательно рассмотрите условие продолжения цикла. В каком случае выполнение цикла продолжается? В каких случаях осуществляется выход из цикла?

Запустите программу на выполнение в среде программирования Pascal.

Как иначе можно решить эту задачу, например, с использованием цикла for? Напишите соответствующую программу.

Оценим сложность рассмотренного алгоритма последовательного поиска, непосредственно зависящую от числа сравнений с искомым элементом. В худшем случае искомый элемент окажется на последнем месте или не будет найден вообще. В таком случае необходимо будет проделать n сравнений, т. е. сложность алгоритма будет равна 0(n).

Пример 4. Поиск максимумов и минимумов.

Имеется массив а[1..n]; требуется найти значение наибольшего (наименьшего) элемента массива.

Алгоритм поиска значения наибольшего (максимального) элемента в неупорядоченном массиве может быть следующим.

1. Установить значение текущего максимума равным первому исследуемому элементу (max := а[1]).
2. Установить счётчик равным 2 (i:= 2).
3. Если исследованы ещё не все элементы (i <= n), то перейти к шагу 4, иначе алгоритм окончен (максимальный элемент равен max).
4. Если рассматриваемый элемент больше, чем текущий максимум (a[i] > max), то max присвоить значение a[i].
5. Перейти к следующему элементу (увеличить i на единицу).
6. Перейти к шагу 3.

Возможная программа, реализующая этот алгоритм на языке Pascal, имеет вид:

Запустите программу на выполнение в среде программирования Pascal.

Как иначе можно решить эту задачу, например, с использованием цикла for? Напишите соответствующую программу.

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

Какие изменения надо внести в программу для поиска индекса максимального (минимального) элемента массива?

Самостоятельно оцените сложность рассмотренного алгоритма.

Cкачать материалы урока