Jednoczesne znajdowanie największego i najmniejszego elementu w zbiorze
Wyróżniamy dwie metody jednoczesnego znajdowania największego i najmniejszego elementu w zbiorze:
- Algorytm naiwny
polega na zastosowaniu algorytmu szukania minimum dla n elementów, usunięciu elementu najmniejszego ze zbioru a następnie zastosowania algorytmu szukania maksimum dla zbioru składającego się z n-1 elementów (czyli pomniejszonego o element najmniejszy)
W algorytmie naiwnym wykonujemy n-1+n-2=2n-3 porównań - Algorytm optymalny – metoda dziel i zwyciężaj
Przy parzystej liczbie elementów wykonujemy najpierw n/2 porównań aby podzielić zbiór na dwie części i w każdej części wykonujemy n/2-1 porównań czyli razem:
n/2 + n/2 -1 + n/2 -1 = 3n/2 -2
Przy nieparzystej liczbie elementów ostatni element pozostaje zapamiętany w zmiennej pomocniczej a na samym końcu porównujemy do z największym i najmniejszym znalezionym elementem. W szczególnym przypadku to właśnie ten ostatni element może być minimalny bądź maksymalny.