Wyszukiwanie liniowe MAX i MIN

O wyszukiwaniu

Algorytm polega na zadeklarowaniu dwóch zmiennych: min oraz max. Obie zmienne mają początkowe wartości równe pierwszemu elementowi na liście. Następnie porównujemy każdy element z min oraz max. Jeśli jakikolwiek jest większy od max to przypisujemy max daną wartość. Tak samo wygląda działanie algorytmu dla wyszukiwania minimum.

Zbadajmy jeszcze złożoność algorytmu. Dla każdego elementu prócz pierwszego wykonamy dwa porównania. Dla n elementowej listy daje to 2(n - 1) porównań. Na tej podstawie można zapisać, że złożoność takiego algorytmu to Θ(n).

Przykład

Prześledźmy wyszukiwanie dla listy L:={4, 3, 5, 1, 2}. Na początek deklarujemy min = max = 4. Następnie dla każdego pozostałego elementu porównujemy go z aktualnymi wartościami min i max.

Implementacja

Napiszemy teraz program, który wczyta listę liczb rzeczywistych, a następnie wywoła funkcję, która wczyta do określonych zmiennych wartość maksymalną i minimalną w tablicy. Drugą część realizuje funkcja findMinMax().

1. void findMinMax(double* lista, int n, double &min, double &max){
2.   min = max = lista [0];
3.   for(int i = 1; i < n; i++){
4.     if(lista[i] < min)
5.       min = lista[i];
6.     if(lista[i] > max)
7.       max = lista[i];
8.   }
9. }

(1.) Funkcja findMinMax() przyjmuje cztery argumenty: lista - wczytana lista liczb rzeczywistych, n - ile elementów ma lista. Pozostałe dwa elementy przekazujemy przez referencję. W ten sposób zmiany będą widoczne poza funkcją. (2.) Przypisujemy min i max wartość pierwszego elementu. (3.) Dla każdego elementu prócz pierwszego (o indeksie 0) (4.) sprawdzamy czy i-ty element jest mniejszy od min. Jeśli tak to zapamiętujemy jego wartość w zmiennej min. (6. 7.) Analogicznie robimy dla zmiennej max.

Testowanie funkcji

Napisaną dotychczas funkcję findMinMax() można sprawdzić przy pomocy poniższej funkcji main():

1. int main () {
2.   int n;
3.   cin >> n;
4.   double* L = new double[n];
5.   for(int i = 0; i < n; i++)
6.     cin >> L[i];
7.   double min, max;
8.   findMinMax(L, n, min, max);
9.   cout << "Element maksymalny w tablicy: " << min;
10.   cout << "\nElement minimalny w tablicy: " << max << endl;
11.   delete[] L;
12.   system("pause");
13.   return 0;
14. }

• Kod źródłowy Implementacja

Indeksy elementów MIN i MAX

Czasami jednak nie chcemy znajdować konkretnych wartości elementów maksymalnych i minimalnych. Punktem zainteresowania może być numer indeksu zarówno elementu MIN jak i MAX. W tym celu zmodyfikujemy funkcję findMinMax():

1. void findMinMaxIndex(double* lista, int n, int &min, int &max){
2.   min = max = 0;
3.   for(int i = 1; i < n; i++){
4.     if(lista[i] < lista[min])
5.       min = i;
6.     if(lista[i] > lista[max])
7.       max = i;
8.   }
9. }

(1.) Nie ma potrzeby przechowywać indeksu jako typ double - tutaj wystarczy wartość całkowitoliczbowa int. (2.) Tym razem wartość początkowa min i max to 0 czyli indeks pierwszego elementu. (3.) Dla każdego elementu (4.) tym razem porównujemy element na pozycji i z elementem na pozycji min i jeśli warunek jest spełniony to (5.) do min zapisujemy wartość i, a nie wartość elementu na pozycji i. Analogicznie robimy dla max.

Testowanie funkcji

W celu przetestowania nowej funkcji findMinMaxIndex() należy dostosować funkcję main():

1. int main () {
2.   int n;
3.   cin >> n;
4.   double* L = new double[n];
5.   for(int i = 0; i < n; i++)
6.     cin >> L[i];
7.   int min, max;
8.   findMinMaxIndex(L, n, min, max);
9.   cout << "Numer elementu maksymalnego: " << min + 1;
10.   cout << "\nNumer elementu minimalnego: " << max + 1;
11.   cout << endl;
12.   delete[] L;
13.   system("pause");
14.   return 0;
15. }

• Kod źródłowy Indeksy elementów MIN i MAX

Zadania

Zadanie 1

Napisz funkcję ilewZakresie(), która wczyta listę liczb całkowito liczbowych i dla wyliczonego zakresu wyliczy ile różnych liczb całkowitoliczbowych można w nim zmieścić.

Przykładowo dla listy [7, 3, 5, 2, 1, 4, 4, 3] program zwróci:

1. 5

• Kod źródłowy Zadanie 1