Сунул нос в Кормена,Лейзерсона,Ривеста... Да ещё задачка №1 (http://www.rsdn.ru/Forum/?mid=1006174

Автор:
Дата: 26.01.05

) навеяла.

Дано: массив чисел.
Найти:
— минимум и максимум
— медиану
за как можно меньшее время.

Очевидно, что для нахождения минимума ИЛИ максимума требуется N-1 сравнений.
То есть, лобовое решение для минимума И максимума — 2N-2.

Лобовое решение для медианы, с модификацией массива — это O(N log N) : быстрая сортировка, затем берём [N/2]-й элемент.

Попробуйте улучшить

PS. Те, кто знает готовые ответы — не спешите. Это же этюд