Element o takich własnościach nosi nazwę lidera. Lidera można znaleźć przy pomocy jednego z opisanych w poprzednim rozdziale algorytmów wyszukiwania najczęstszej wartości w zbiorze. Po znalezieniu takiej wartości sprawdzamy, czy liczba jej wystąpień jest większa od liczby połowy elementów zbioru Z. Jeśli tak, to mamy lidera. Jeśli nie, to zbiór Z  nie posiada lidera.

Istnieje jednakże prostszy i szybszy algorytm, który korzysta z następującego twierdzenia:

Dowód tego twierdzenia jest bardzo prosty. Oznaczmy przez n _L  liczbę elementów będących liderami. Zbiór Z  posiada n  elementów, zatem liczba pozostałych elementów wynosi n  - n _L. Zachodzi nierówność:

n _L  > n  - n _L

Przypadek 1

Ze zbioru Z usuwamy dwa elementy, które nie są liderami. W tym przypadku n _L nie zmniejsza się, lecz zmniejsza się o 2 liczba elementów n. Otrzymamy zatem:

Jeśli pierwsza nierówność była prawdziwa (a była z założenia, iż n _L  jest liczebnością liderów ), to tym bardziej będzie prawdziwa druga nierówność. Wynika z tego, iż usunięcie dwóch elementów nie będących liderami nie wpływa na występowanie lidera.

Przypadek 2

Ze zbioru Z  usuwamy jeden element lidera oraz jeden element nie będący liderem. Zmniejszeniu o 1 ulega zatem liczba liderów, a liczba elementów maleje o 2. Otrzymujemy:

Otrzymaliśmy nierówność wyjściową, w której od obu stron odjęto tę samą liczbę -1. Zatem nierówność jest wciąż prawdziwa, z czego wynika, iż usunięcie ze zbioru jednego lidera i jeden element nie będący liderem nie wpływa na występowanie lidera.

Innych przypadków nie ma, zatem dowiedliśmy prawdziwości twierdzenia.

Z powyższego twierdzenia bezpośrednio wynikają dwie dalsze własności:

Zamiast faktycznie wyrzucać ze zbioru elementy różne – co jest dosyć trudne, możemy wykonać operację odwrotną. Będziemy zliczali elementy o równych wartościach – wystarczy wtedy zapamiętać wartość elementu oraz ilość jej wystąpień. Algorytm pracuje w sposób następujący:

Licznik elementów równych L  ustawiamy na zero. Rozpoczynamy przeglądanie elementów zbioru od pierwszego do ostatniego. Jeśli licznik elementów równych L  jest równy 0, to kolejny element zbioru zapamiętujemy, zwiększamy licznik L  o 1 i wykonujemy kolejny obieg pętli dla następnego elementu. Jeśli licznik L  nie jest równy zero, to sprawdzamy, czy bieżący element jest równy zapamiętanemu. Jeśli tak, to mamy dwa elementy równe – zwiększamy licznik L  o 1. W przeciwnym razie licznik L  zmniejszamy o 1 – odpowiada to wyrzuceniu ze zbioru dwóch elementów różnych. W obu przypadkach wykonujemy kolejny obieg pętli.

Jeśli zbiór Z  posiadał lidera, to liczba elementów równych jest większa od liczby elementów różnych. W takim przypadku zapamiętana wartość jest liderem. Aby to potwierdzić, zliczamy liczbę wystąpień tej wartości w zbiorze Z. Jeśli jest ona większa od liczby połowy elementów, to mamy lidera. W przeciwnym razie zbiór Z  nie posiada lidera.

Algorytm posiada liniową klasę złożoności obliczeniowej O ( n  ), jest zatem bardziej efektywny od opisanych w poprzednim rozdziale algorytmów wyszukiwania najczęstszej wartości.

Algorytm wyszukiwania lidera w zbiorze

// Wyszukiwanie lidera
// Data:   4.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

const N = 80;

var
  Z : array [ 0..N-1 ] of integer;
  i, L, W : integer;
  t : boolean;

begin
  randomize;

  // Wypełniamy tablicę

  W := random ( 100 );
  for i := 0 to N - 1 do
    if random ( 2 ) = 1 then Z [ i ] := random ( 100 )
    else                  Z [ i ] := W;

  // Wyszukujemy lidera

  L := 0;
  for i := 0 to N - 1 do
    if L = 0 then
    begin
      W := Z [ i ]; L := 1;
    end
    else if W = Z [ i ] then inc ( L )
         else           dec ( L );

  // Sprawdzamy, czy mamy lidera

  if L = 0 then t := false
  else
  begin
    L := 0;
    for i := 0 to N - 1 do if W = Z [ i ] then inc ( L );
    t := L > N div 2;
  end;

  // Wyświetlamy tablicę

  for i := 0 to N - 1 do
    if t and ( Z [ i ] = W ) then write ( ' >', Z [ i ] :2 )
    else                        write ( Z [ i ] :4 );

  // Wyświetlamy wyniki

  writeln;
  if t then writeln ( W, ' : ', L )
  else      writeln ( 'BRAK LIDERA' );
  writeln

end.

// Wyszukiwanie lidera
// Data:   4.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N = 80;

int main( )
{
  int Z [ N ], i, L, W;
  bool t;

  srand ( ( unsigned )time ( NULL ) );

  // Wypełniamy tablicę

  W = rand( ) % 100;
  for( i = 0; i < N; i++ )
    if( rand( ) % 2 ) Z [ i ] = rand( ) % 100;
    else              Z [4 i ] = W;

  // Wyszukujemy lidera

  L = 0;
  for( i = 0; i < N; i++ )
    if( !L )
    {
      W = Z [ i ]; L = 1;
    }
    else if( W == Z [ i ] ) L++;
         else              L--;

  // Sprawdzamy, czy mamy lidera

  if( !L ) t = false;
  else
  {
    L = 0;
    for( i = 0; i < N; i++ ) if( W == Z [ i ] ) L++;
    t = L > N / 2;
  }

  // Wyświetlamy tablicę

  for( i = 0; i < N; i++ )
    if( t && ( Z [ i ] == W ) ) cout << " >" << setw ( 2 ) << Z [ i ];
    else                    cout << setw ( 4 ) << Z [ i ];

  // Wyświetlamy wyniki

  cout << endl;
  if( t ) cout << W << ": " << L << endl;
  else  cout << "BRAK LIDERA\n";
  cout << endl;
  return 0;
}

' Wyszukiwanie lidera
' Data:   4.05.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Const N = 80

Dim As Integer Z ( N-1 ), i, L, W, t

Randomize

' Wypełniamy tablicę

W = Cint ( Rnd * 99 )
For i = 0 To N - 1
  If Rnd > 0.5 Then
    Z ( i ) = Cint ( Rnd * 99 )
  Else
    Z ( i ) = W
  End If
Next

' Wyszukujemy lidera

L = 0
For i = 0 To N - 1
  If L = 0 Then
    W = Z ( i ): L = 1
  Elseif W = Z ( i ) Then
    L += 1
  Else
    L -= 1
  End If
Next

' Sprawdzamy, czy mamy lidera

If L = 0 Then
  t = 0
Else
  L = 0
  For i = 0 To N - 1
    If W = Z ( i ) Then L += 1
  Next
  t = ( L > N \ 2 )
End If

' Wyświetlamy tablicę

For i = 0 To N - 1
  If t And ( Z ( i ) = W ) Then
    Print Using " >##";Z ( i );
  Else
    Print Using "####";Z ( i );
  End If
Next

' Wyświetlamy wyniki

Print
If t Then
  Print W;": ";L
Else
  Print "BRAK LIDERA"
End If

Print

End