Максимальные и минимальные значения массива

Question

Дается массив из n чисел, где n - четное число. Необходимо определить максимум, а также минимум этих n чисел. Мне нужно знать, какие сравнения необходимы?

Answer 1

Это можно сделать в O (n) времени.

Вы можете проверить это link для справки

Answer 2

Это может быть сделано с помощью 3*n/2-2 сравнений.

Для n == 2 просто сравните два числа. Теперь предположим, что у нас есть минимум и максимум для первых чисел n-2. Сравните оставшиеся два числа, затем сравните большую с предыдущим максимумом и меньшим, чем предыдущий минимум.

Answer 3

Для несортированного массива это можно сделать примерно в 1.5n сравнениях. Вы можете сделать это, сравнивая пары элементов массива и сохраняя min и локальные max. Вы сделали n/2 сравнения, чтобы найти (местные) макс и n/2, чтобы найти мин. Таким образом, в этой фазе n.

Теперь вы переходите к местным макс и мин и находите глобальные максимальные и минимальные значения. Это также приведет к сравнениям n/2. Таким образом, n + n/2 = 1.5n.

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