Jednoczesne wyszukiwanie min i max

powrót

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:

  • do zmiennych MIN i MAX przypisujemy pierwszą liczbę: MIN = MAX = 4
  • następny element zbioru sprawdzamy, czy jest większy niż MAX (if(6 > 4))
    • jeśli tak, to zmienną MAX nadpisujemy tą wartością (MAX = 6)
  • teraz sprawdzamy, czy ten element jest mniejszy od MIN (if(6 < 4))
    • jeśli tak, to zmienną MIN zastępujemy tą wartością (w tym przypadku warunek nie jest spełniony)
  • czynność tą postarzymy do wyczerpania liczb w zbiorze

Ostatecznie otrzymujemy:

  • MIN = 1
  • MAX = 8

 

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++:

#include<iostream>
#include<cstdlib>
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;
	
	system("pause");
	return 0;
}
 

 

Out: 

  • MAX: 9
  • MIN: 0