Поиск максимумов и минимумов

Усложним задачу. Пусть нам требуется найти минимальный элемент в неупорядоченном массиве. Оказывается, что и эта задача имеет линейную сложность, и для поиска минимального (максимального) элемента в неупорядоченном массиве требуется n – 1 сравнение. Запишем алгоритм поиска максимального элемента в текстовой форме.

Алгоритм поиска максимального элемента в неупорядоченном массиве:

1. Установить счетчик равным 1 (i = 1).

2. Положим значение текущего максимума равным первому исследуемому элементу (max = a₁).

3. Если исследованы еще не все элементы (i < n), то перейти к шагу 5, иначе алгоритм окончен (максимальный элемент равен max).

4. Перейти к следующему элементу (увеличить i на единицу).

5. Если рассматриваемый элемент больше, чем текущий максимум (a_i > max), то значение a_i присвоить max.

6. Перейти к шагу 4.

Приведем блок-схему аналогичного алгоритма поиска минимального элемента:

Скачать текст программы

Можно еще усложнить задачу и найти одновременно максимальный и минимальный элементы. Скорректируем вышеприведенный алгоритм.

Алгоритм одновременного поиска максимального и минимального элементов в неупорядоченном массиве:

1. Установить счетчик равным 1 (i = 1).

2. Положим значения текущего минимума и текущего максимума равными первому исследуемому элементу (min = a₁, max = a₁).

3. Если исследованы еще не все элементы i < n), то перейти к шагу 4, иначе алгоритм окончен (минимальный и максимальный элементы равны min и max соответственно).

4. Перейти к следующему элементу (увеличить i на единицу).

5. Если текущий элемент меньше чем минимум (a_i < min), то присвоить min значение a_i, иначе если текущий элемент больше, чем максимум (a_i > max), то присвоить max значение a_i

6. Перейти к шагу 3.

Запишем этот алгоритм в виде блок-схемы: Скачать текст программы

Сложность этого алгоритма равна 2 · (n – 1). Возникает вопрос, существует ли алгоритм одновременного поиска минимального и максимального элемента, сложность которого меньше, чем 2 · (n – 1)? Оказывается, такой алгоритм существует, и его сложность равна 3 · (n/2).

Эффективный алгоритм поиска максимального элемента в неупорядоченном массиве:

 

1. Разбить массив на пары (получим n/2 пар, при нечетном n плюс еще одна неполная пара).

2. Упорядочить по возрастанию каждую пару (при выполнении этого шага будет выполнено (n/2) сравнений). Тогда в массиве на всех нечетных местах будут стоять минимальные для каждой пары числа, а на всех четных местах – максимальные.

3. Найти минимальное число, осуществляя поиск только среди элементов, стоящих на нечетных местах. При этом если у нас есть неполная пара, то в качестве начального значения переменной min взять значение элемента неполной пары (при выполнении этого шага будет выполнено (n/2) сравнений).

4. Найти максимальное число, осуществляя поиск только среди элементов, стоящих на четных местах. При этом если у нас есть неполная пара, то в качестве начального значения переменной max взять значение элемента неполной пары (при выполнении этого шага будет выполнено (n/2) сравнений).

Всего сравнений в этом алгоритме 3 · (n/2).

Скачать текст программы