Szukanie lidera 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:
ciąg liczb

nie posiada lidera, ponieważ żadna z liczb nie wystąpiła co najmniej razy.

Ciąg

także nie posiada lidera, natomiast dla  liczb

liderem jest liczba .

Strategia jest następująca. Przeszukujemy liniowo kolejne elementy i w danym etapie dwa różne elementy zbioru wykreślamy - tak jak by ich nie było. Jeśli lider występuje w zbiorze, to jego "pozycja" w otrzymanym podzbiorze się nie zmieni. Przeanalizujmy następujący przykład:

i pozostał na zbiór, w którym nadal mamy lidera:

Redukując w ten sposób elementy dochodzimy do sytuacji, gdy pozostanie element, który jest kandydatem na lidera. Musimy teraz tylko liniowo zliczyć i sprawdzić, czy dana wartość występuje więcej niż razy.

Warto podkreślić, że znaleziony element nie musi być liderem. Prześledźmy przykład, w którym nie ma lidera:

Po wykreśleniu dwóch początkowych wyrazów pozostaje podzbiór

,

w którym jest lider.

W programie przedstawionym poniżej ważną rolę odgrywa zmienna . Odpowiedzialna jest ona za kontrolowanie wykreślania dwóch elementów o różnych wartościach. Jeśli wykreślimy wszystkie elementy, oznacza to, że żadna wartość nie spełnia oczekiwań. Przeanalizujmy przypadek:

W przypadku znalezienia liczby różnej od aktualnego lidera, wykreślamy ją zmniejszając wartość zmiennej . Gdy znajdziemy taką samą, wartość zmiennej inkrementujemy. Jeśli  będzie liczbą większą od zera, oznacza to, że zmienna przechowuje potencjalnego lidera zbioru.

Szukanie elementów ciągu

Załóżmy że mamy daną tablicę n-elementów i chcemy odnaleźć w niej element minimalny (bądź maksymalny). Niech będzie to tablica a o indeksach od 1 do n. Czyli kolejne jej elementy oznaczymy: a[1], a[2], a[3], ..., a[n-1], a[n].

By odnaleźć element minimalny podejmiemy następujące kroki:

• na początku zainicjujemy wynik pierwszą wartością z tablicy, czyli a[1],
• następnie przejdziemy po kolejnych elementach tablicy (rozpoczynając od drugiego) i jeżeli dany element tablicy jest mniejszy od naszego wyniku, to zaktualizujemy nasz wynik przypisując do niego ten element,
• po przejściu po wszystkich elementach otrzymamy w wyniku element najmniejszy w tablicy.

Przeszukiwanie liniowe

Przeszukiwanie liniowe (lub wyszukiwanie 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ść

Algorytm przeszukiwania liniowego:

Dane	n - ilość elementów zbioru x1 .. xn - elementy zbioru y - szukany element
Wyniki	jeśli y należy do zbioru: i - indeks pierwszego wystąpienia elementu y w zbiorze, w przeciwnym przypadku informacja, że y nie należy do zbioru,
Krok 1	dla i = 1, 2 .... n: jeśli y = xi to i jest wynikiem, zakończ algorytm {element y po raz pierwszy wystąpił w zbiorze na pozycji i-tej}, w przeciwnym przypadku w zbiorze nie ma elementu równego y, zakończ algorytm.