Poszukiwanie zaczynamy, naturalnie, od elementu  który staje się kandydatem na minimum. Jeśli teraz  to  pozostaje kandydatem na minimum, a jeśli, przeciwnie,   to kandydatem na minimum staje się  Łatwo zobaczyć, co będzie dalej: każdy kolejny element tablicy,  porównujemy z obecnym kandydatem na minimum i aktualizujemy tegoż kandydata, jeśli  okazał się od niego mniejszy (patrz pseudokod na marginesie).

Łatwo oszacować, ile operacji wykonujemy w tym algorytmie: mamy dokładnie  porównań oraz co najwyżej  przypisań. Co prawda, powyższy algorytm jest naprawdę prosty, ale zawsze można dla pewności spytać: czy dałoby się lepiej? Na przykład, czy można znaleźć minimum w tablicy, wykonując mniej niż   porównań?

Rys. 1 Graf porównań odpowiadający tablicy  po wykonaniu porównań:  z  z   z   z   i  z 

Intuicyjnie widać, że nie, czyli że trzeba wykonać co najmniej  porównań. Tę intuicję można także wesprzeć formalnym uzasadnieniem. Ustalmy pewien algorytm wyznaczający minimum w tablicy  Dla danego przebiegu (wykonania) tego algorytmu możemy skonstruować graf porównań, którego wierzchołki  reprezentują numery elementów w tablicy, a krawędź łączy dwa wierzchołki wtedy, gdy odpowiadające im elementy zostały porównane w tym przebiegu algorytmu (patrz Rys. 1). Wystarczy teraz zauważyć, że jeśli na końcu takiego przebiegu graf porównań nie jest spójny, to rozważany algorytm nie może być poprawny: bez dodatkowych porównań nie jesteśmy w stanie stwierdzić, w której spójnej składowej faktyczne minimum się znajduje. Ponieważ graf spójny o  wierzchołkach musi mieć co najmniej  krawędzi, więc rzeczywiście potrzebnych jest  porównań.

Skoro wiemy już wszystko o wyznaczaniu minimum, to może teraz zastanowimy się, jak efektywnie znaleźć drugi co do wielkości element tablicy? Będzie to właśnie tytułowe second min.

Najprościej wykorzystać poprzedni algorytm: znajdujemy minimum, usuwamy je z tablicy (np. odpowiednio je oznaczając), po czym znajdujemy minimum wśród pozostałych elementów tablicy. W ten sposób wykonujemy  porównania. Można to jednak zrobić lepiej, jeśli tylko wykorzystamy inny algorytm wyszukiwania minimum.

Rys. 2 Turniej związany z tablicą  Zwycięzcą (czyli minimum) jest

Pokażemy, jak znaleźć second min za pomocą  porównań. Zaczynamy od zbudowania turnieju, czyli „drabinki meczów” między elementami tablicy : w każdym „meczu” mniejszy element wygrywa i w ten sposób wyłaniany jest zwycięzca, czyli minimum. Gdyby  było potęgą dwójki, ów turniej moglibyśmy reprezentować jako pełne drzewo binarne; w ogólnym przypadku na ostatnim poziomie drzewa mogą występować luki (patrz Rys. 2).

Widzimy, że za pomocą turnieju znów udaje nam się wyznaczyć minimum w tablicy za pomocą  porównań (meczów). Rzeczywiście, po każdym porównaniu jeden element odpada z turnieju. A gdzie w drabince turniejowej znajduje się element second min? Otóż mógł on przegrać w turnieju jedynie z elementem min – no bo z nikim innym. Na każdym poziomie drabinki jest co najwyżej jeden element, który przegrał z minimum, czyli łącznie mamy co najwyżej  kandydatów na second min. Przykładowo, w turnieju z rysunku 2 kandydatami na second min są    i  Wystarczy zatem wybrać minimum spośród tych właśnie elementów, do czego, jak wiemy, potrzeba już tylko  porównań. Łącznie wykonaliśmy  porównań, czyli tyle, ile chcieliśmy.

Naturalnie nasuwa się pytanie, czy da się lepiej, tzn. czy aby na pewno przy wyznaczaniu second min trzeba wykonać  porównań. W związku z uwagą na marginesie warto tu zadać bardziej precyzyjne pytanie: czy każdy algorytm znajdujący second min wykonuje w pesymistycznym przypadku co najmniej  porównań? Innymi słowy, czy każdemu takiemu algorytmowi możemy tak złośliwie dobrać dane wejściowe, żeby musiał wykonać podaną liczbę porównań? Odpowiedź na to pytanie jest twierdząca, co spróbujemy uzasadnić. Odtąd założymy dla uproszczenia, że wszystkie elementy w tablicy  są różne; poniższe rozumowanie można lekko zmodyfikować tak, aby działało także w przypadku powtarzających się elementów w  Przede wszystkim musimy wyjaśnić jedną rzecz: każdy algorytm wyznaczający second min musi przy okazji znaleźć element min, tzn. na końcu jego działania musi być jednoznacznie wyznaczone, który element tablicy jest minimalny. Faktycznie, gdyby na końcu algorytmu wciąż byli dwaj kandydaci na minimum (czyli mniejsi od wszystkich elementów, z którymi byli porównywani), to któryś z nich mógłby równie dobrze być elementem second min.

Aby dokończyć rozumowanie, musimy pokazać pewną kluczową i trochę nieintuicyjną własność. Otóż w każdym algorytmie wyznaczającym minimum w tablicy (a więc także w każdym wyznaczającym second min) element min jest porównywany w pesymistycznym przypadku co najmniej  razy.

Zanim to pokażemy, zastanówmy się, co nam to da. Przyjrzyjmy się grafowi porównań algorytmu wyznaczającego second min. Wiemy – a dokładniej, będziemy wiedzieli, jak udowodnimy – że w pesymistycznym przypadku z elementu min wychodzi w tym grafie co najmniej  krawędzi. Usuńmy z grafu element min; reszta musi pozostać spójna, gdyż w przeciwnym przypadku mielibyśmy w niej więcej niż jednego kandydata na second min. Stąd, reszta grafu musi zawierać co najmniej  krawędzie, czyli łącznie musi być co najmniej tyle krawędzi, ile należało pokazać.

Pozostał nam już tylko dowód tajemniczej własności wszystkich algorytmów wyznaczających minimum. Teraz całą sytuację przedstawimy jako grę...

Mamy dwoje graczy. Pierwszy gracz będzie symulował działanie algorytmu wyszukującego minimum, czyli będzie zadawał pytania postaci: „Czy ?”. Zawartość tablicy  nie jest jednak znana a priori. Drugi gracz odpowiada na pytania pierwszego, przy czym jego odpowiedzi nie mogą nigdy być sprzeczne – to znaczy, że po każdej sekwencji jego odpowiedzi musi istnieć zawartość tablicy  zgodna ze wszystkimi odpowiedziami, jakich udzielił. Celem pierwszego gracza jest wyznaczyć minimum w tablicy, wykonując mniej niż  porównań dotyczących min, a celem drugiego – spowodować, żeby pierwszy gracz musiał zadać co najmniej  pytań dotyczących min.

Podamy teraz strategię wygrywającą dla drugiego gracza. Z każdym elementem tablicy  zwiążemy licznik ; początkowo wszystkie liczniki są ustawione na 1. Będziemy dbali o to, aby wszystkie liczniki były zawsze nieujemne i całkowite oraz aby ich suma była równa  Będziemy też utrzymywać niezmiennik, że wszystkie dodatnie liczniki odpowiadają kandydatom na minimum, czyli elementom, które w żadnym porównaniu nie okazały się większe.

Metoda odpowiadania na pytania jest następująca: jeśli pierwszy gracz chce porównać elementy  i  to odpowiadamy, że mniejszy jest ten element, który ma nie mniejszy licznik. Wówczas licznik mniejszego elementu zwiększamy o wartość licznika większego elementu, a drugi z tych liczników zerujemy (patrz przykład na rysunku 3). Jeśli tylko przed wykonaniem zapytania co najmniej jeden z liczników    był niezerowy, to postępując zgodnie z tą metodą, na pewno nigdy nie udzielimy odpowiedzi sprzecznej z poprzednimi, gdyż porównanie wygra kandydat na minimum. A jeżeli oba liczniki były zerowe, to musimy po prostu odpowiedzieć tak, żeby nie skłamać: jeśli na podstawie dotychczasowych odpowiedzi można wywnioskować, który z elementów    jest mniejszy, to odpowiadamy zgodnie z prawdą, a jeśli nie, to odpowiadamy jakkolwiek.

Łatwo sprawdzić, że podana metoda spełnia wszystkie żądane niezmienniki. Na końcu gry element minimalny musi mieć licznik równy  a pozostałe liczniki muszą być zerowe. A ponieważ po każdym pytaniu licznik elementu minimalnego może się co najwyżej podwoić, więc łącznie wykonaliśmy na tym liczniku co najmniej  operacji. To kończy dowód!