Załóżmy że mamy daną tablicę n-elementów i chcemy odnaleźć w niej zadany element x. 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].

Jeżeli elementy w tej tablicy są posortowane, to możemy użyć bardzo szybkiego algorytmu wyszukiwania połówkowego, zwanego też wyszukiwaniem binarnym. Poniżej przedstawię jego wersję dla tablicy posortowanej rosnąco. Nazwa tego algorytmu pochodzi od sposobu w jaki szukany jest element. Załóżmy, że początkowy indeks naszej tablicy oznaczony jest indeksem l a końcowy indeks tablicy oznaczony jest p. Na początku oczywiście l = 1 a p = n. Dzielimy tą tablicę na pół elementem o indeksie równym s = (l + p) / 2, przy czym dzielenie to jest dzieleniem bez reszty, tak by uzyskać liczbę całkowitą (w końcu indeksy elementów w naszej tablicy są liczbami całkowitymi). Sprawdzamy czy element o indeksie s jest szukanym elementem, jeżeli tak to kończymy działanie algorytmu gdyż odnaleźliśmy szukany element. W przeciwnym razie sprawdzamy czy element pod indeksem s jest większy od szukanego. Jeżeli tak jest to wiemy, że elementy o indeksach s+1, s+2, ...p również są większe (wynika, to z faktu, że tablica jest posortowana rosnąco). Zatem wiemy już że tamtej części nie ma co szukać, ustawiamy zatem indeks końca tablicy p na wartość s-1 i powtarzamy dzielenie tej tablicy na pół tak, jak już to było opisane wcześniej. Gdy element pod indeksem s jest mniejszy od szukanego to wiemy, że również elementy o indeksach s-1, s-2, ...l są mniejsze od elementu szukanego (wynika, to z faktu, że tablica jest posortowana rosnąco). Zatem wiemy już że tamtej części nie ma co szukać, ustawiamy zatem indeks początku tablicy l na wartość s+1 i powtarzamy dzielenie tej tablicy na pół tak, jak już to było opisane wcześniej. Opisane czynności wykonujemy tak długo aż znajdziemy szukany element bądź wskaźnik początku tablicy l będzie większy od wskaźnika końca tablicy p. Jeżeli tak się stanie oznacza to, że szukanego elementu nie ma w przeszukiwanej tablicy.

Operację szukania połówkowego (binarnego) możemy zapisać następującym schematem blokowym:



Algorytm ten ma bardzo dobrą złożoność obliczeniową wynoszącą O(log n), co oznacza, że czas potrzebny na wyszukanie elementu tą metodą rośnie w sposób logarytmiczny wraz z liniowym wzrostem liczby elementów w przeszukiwanej tablicy.


Niech będzie dana tablica 5-elementowa, a = {1, 2, 4, 6, 7}.
Poszukajmy w niej element x = 2.
Na początku l = 1, p = 5.
Wybieramy element środkowy s = (1 + 5) / 2 = 3.
Sprawdzamy czy a[3] jest równe 2? Nie, element ten jest równy 4, jest on większy od 2 zatem modyfikujemy p = s - 1 = 3 - 1 = 2.
Wybieramy element środkowy s = (1 + 2) / 2 = 1.
Sprawdzamy czy a[1] jest równe 2? Nie, element ten jest równy 1, jest on mniejszy od 2 zatem modyfikujemy l = s + 1 = 1 + 1 = 2.
Wybieramy element środkowy s = (2 + 2) / 2 = 2.
Sprawdzamy czy a[2] jest równe 2? Tak, znaleźliśmy szukany element pod indeksem 2.

Poszukajmy teraz element x = 5.
Na początku l = 1, p = 5.
Wybieramy element środkowy s = (1 + 5) / 2 = 3.
Sprawdzamy czy a[3] jest równe 5? Nie, element ten jest równy 4, jest on mniejszy od 5 zatem modyfikujemy l = s + 1 = 3 + 1 = 4.
Wybieramy element środkowy s = (4 + 5) / 2 = 4.
Sprawdzamy czy a[4] jest równe 5? Nie, element ten jest równy 6, jest on większy od 5 zatem modyfikujemy p = s - 1 = 3.
W tym momencie l jest większe od p, zatem kończymy wyszukiwanie. Elementu o wartości 5 nie ma w przeszukiwanej tablicy.

Przykład w JavaScript

Podaj szukaną liczbę: Szukaj