Algorytm, który wyszukuje minimum i maksimum w optymalny sposób znajduje się w tym miejscu. Omawiany algorytm będzie oparty na zasadzie klasycznego wyszukiwania tych elementów i jest opisany tutaj.
Zastosowany algorytm wykonuje $$2\cdot n-2$$ porównań elementów zbioru.
Prześledźmy ciąg:
$$4,\ 6,\ 3,\ 1,\ 8,\ 4$$
Postępujemy według schematu:
Ostatecznie otrzymujemy:
Algorytm ten można wykorzystywać przy wyszukiwaniu rozstępu zbioru. Rozstęp zbioru to różnica między wartością maksymalną i minimalną. |
Rozwiązanie w C++:
//algorytm.edu.pl
#include<iostream>
using namespace std;
int main()
{
int tab[] = {1, 3, 4, 5, 2, 0, 6, 9, 8}, MIN, MAX;
MIN = MAX = tab[0];
for(int i=1; i < 9; i++)
{
if(tab[i] > MAX)
MAX = tab[i];
if(tab[i] < MIN)
MIN = tab[i];
}
cout<<"MAX: "<<MAX<<"\nMIN: "<<MIN<<endl;
return 0;
}
Out: