Wyszukiwanie w tablicy

Bardzo często naszym zadaniem jest sprawdzenie, czy konkretna liczba (np. klucz X) istnieje w ogromnej tablicy, a jeśli tak, to na jakim znajduje się indeksie. Możemy to zrobić w sposób prosty, lub szybki.

Wyszukiwanie Liniowe (z wartownikiem)

Najprostsza metoda polega na przejrzeniu tablicy element po elemencie, od początku do końca, aż znajdziemy to, czego szukamy. Złożoność to $O(n)$.

Klasyczne podejście wykorzystuje zwykłą pętlę. Istnieje jednak optymalizacja nazywana wyszukiwaniem z wartownikiem. W tej metodzie doczepiamy na sam koniec tablicy nasz szukany klucz X (nazywany właśnie wartownikiem). Dziêki temu pętla while nie musi za każdym razem sprawdzać, czy nie wyjechała poza zakres tablicy (indeks i < n), bo i tak na pewno zatrzyma się na końcu!

Python

def wyszukaj_liniowo(T, x):
    T.append(x)  # Dodajemy wartownika
    
    i = 0
    while T[i] != x:
        i += 1
        
    T.pop() # Usuwamy wartownika z końca
    
    if i == len(T):
        return -1
    return i

C++

#include <iostream>
#include <vector>
using namespace std;

int wyszukajLiniowo(vector<int>& T, int x) {
    T.push_back(x);
    
    int i = 0;
    while (T[i] != x) {
        i++;
    }
    
    T.pop_back();
    if (i == T.size()) {
        return -1;
    }
    return i;
}

Wyszukiwanie Binarne (Dla POSORTOWANEJ tablicy)

Jeśli wiemy, że tablica jest posortowana rosnąco, wyszukiwanie element po elemencie to ogromne marnotrawstwo czasu.

Zamiast tego używamy wyszukiwania binarnego (podobnie jak szukamy hasła w słowniku).

1. Bierzemy element ze środka tablicy.
2. Jeśli trafiliśmy, to świetnie!
3. Jeśli środkowy element jest mniejszy od szukanego, wiemy, że szukany musi znajdować się w prawej połówce. Odrzucamy lewą.
4. Jeśli jest większy, to szukany znajduje się w lewej połówce.
5. Powtarzamy proces dzielenia na pół, aż znajdziemy element lub przedział zmniejszy się do zera.

Python

def wyszukiwanie_binarne(T, x):
    L = 0
    P = len(T) - 1
    
    while L <= P:
        srodek = (L + P) // 2
        
        if T[srodek] == x:
            return srodek
            
        if T[srodek] < x:
            L = srodek + 1
        else:
            P = srodek - 1
            
    return -1

tab = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(wyszukiwanie_binarne(tab, 23)) # Zwróci indeks 5

C++

#include <iostream>
#include <vector>
using namespace std;

int wyszukiwanieBinarne(vector<int>& T, int x) {
    int L = 0;
    int P = T.size() - 1;
    
    while (L <= P) {
        int srodek = (L + P) / 2;
        
        if (T[srodek] == x) return srodek;
        
        if (T[srodek] < x) L = srodek + 1;
        else P = srodek - 1;
    }
    return -1;
}

int main() {
    vector<int> tab = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    cout << wyszukiwanieBinarne(tab, 23) << endl;
    return 0;
}

[!TIP] Dla dociekliwych: Pułapka przepełnienia (Integer Overflow) Zwróć uwagę na liczenie środka: srodek = (L + P) / 2. W językach takich jak C++ lub Java, jeśli indeksy tablicy są kosmicznie wielkie, operacja L + P może przekroczyć maksymalną wartość typu int! Aby uchronić się przed przepełnieniem (integer overflow), w produkcyjnym kodzie środek oblicza się tak: srodek = L + (P - L) / 2.