Lider w zbiorze

Lider to taka wartość w zbiorze  elementów, która powtarza się więcej niż  razy. Jeśli istnieje taka wartość, to jest ona tylko jedna. Prześledźmy przykłady:

a)  8,8,1,4,3,8,8,9,0,88 - w tym ciągu liczba 8 jest liderem, bo na 11 elementów tego zbioru, aż sześć elementów przypada liczbie osiem

b) Czy Chińczycy są liderem w liczbie ludności na Ziemi? - NIE, bo na 7 miliardów ludzi, Chińczycy stanowią zaledwie 2/7 ludności ziemskiej

 zapis w C++

Maksymalny i minimalny element

Omawiamy algorytm optymalnie wyszukuje  ze zbioru liczb jednocześnie wartość najmniejszą i największą wykonując minimalną liczbę porównań. Metoda ta zaliczana jest do technik programistycznych typu "dziel i zwyciężaj". 

Zasada algorytmu jest bardzo prosta. Do badania bierzemy jednorazowo po dwie liczby, porównujemy je ze sobą i większą z nich przydzielamy do zbioru potencjalnych maksimów, a mniejszą lub równą do potencjalnych minimów. W ten sposób otrzymaliśmy dwa zbioru, gdzie w pierwszym występuje wartość, która jest maksymalna oraz w drugim wartość, która jest minimalna. Aby znaleźć teraz maksimum i minimum wykorzystujemy klasyczne przeszukiwanie liniowe dla tych dwóch podzbiorów. Szukanie to można wykonywać już podczas wczytywania danych nie wykorzystując tablic.

Liniowe przeszukiwanie ciągu liczbowego z wartownikiem.

"Wartownik", to taka wartość, którą ustawiamy na końcu zbioru. Cechuje się ona tym, że nie występuje w badanym ciągu. Jeśli na nią natrafimy to mamy pewność, że przeszukaliśmy już cały zbiór i szukana wartość nie istnieje.

W naszym przykładzie zakładamy, że zbiór składa się z liczb naturalnych. Ilość liczb jest mniejsza od  Jako wartownik posłuży nam liczba  (nie jest to liczba naturalna i nie wystąpi wcześniej).

Prześledźmy przykład:

Załóżmy, że chcemy wyszukać liczbę . Jak widać znajduje się ona na pozycji  i ta liczba powinna znaleźć się na wyjściu.

Gdy spróbujemy wyszukać liczbę , algorytm zatrzyma się na wartości wartownika. Na wyjściu powinien pojawić się stosowny komunikat.

Przeszukiwanie ciągu liczbowego.

Przeszukiwanie liniowe (lubwyszukiwanie sekwencyjne) to najprostszy algorytm wyszukiwania informacji w ciągu danych, np. zapisanych w tablicy lub na liście. Polega na porównywaniu żądanego klucza z kolejnymi kluczami z sekwencji danych – wyszukiwanie kończy się powodzeniem, gdy zostanie znaleziony klucz, albo niepowodzeniem, gdy zostaną przejrzane wszystkie klucze.

Liczba koniecznych porównań zależy wprost od położenia szukanego elementu w sekwencji danych – wynosi od 1 do , gdzie  to całkowita liczba elementów. Algorytm ma złożoność 

Wyszukiwanie liniowe może być jedynym sposobem wyszukiwania, gdy nie wiadomo niczego na temat kolejności kluczy.

Dla dużej liczby danych algorytm jest bardzo nieefektywny, jednak gdy danych jest względnie mało, jest z powodzeniem stosowany (np. w tablicach mieszających, w których problem kolizji rozwiązuje się metodą łańcuchową).