Wyszukiwanie binarne

Wyszukiwanie binarne (binsearch) to sposób szukania elementu w posortowanej liście, który opiera się na zasadzie “Dziel i zwyciężaj”. Dzięki temu algorytmowi unikamy sprawdzania wszystich elementów po kolei.

Schemat działania algorytmu:

Posortowana tablica: Najpierw sortujemy tablicę, którą będziemy przeszukiwać w odpowiedniej kolejności, np. od najmniejszego do największego elementu.
Dziel i zwyciężaj: Porównujemy środkowy element tablicy do poszukiwanego elementu. Jeśli są one sobie równe, algorytm kończy swoje działanie. W przeciwnym przypadku sprawdzamy, czy szukany element jest większy czy mniejszy od środkowego. Jeśli jest większy, powtarzamy proces dla przedziału od środkowego elementu do końca tablicy, a jeśli jest mniejszy od początku tablicy do środkowego elementu.
Powtarzamy proces: Teraz powtarzamy ten proces dla nowej, mniejszej listy. I tak dalej, aż znajdziemy szukany element.

Przykładowa implementacja:

Korzystając z wyszukiwania binarnego napiszmy następujący program:

Napisz program, który będzie implementował algorytm wyszukiwania binarnego w posortowanej tablicy liczb całkowitych.

Wejście: W pierwszym wierszu wejścia znajdują się dwie liczby całkowite oddzielone spacją: $n$ – liczba elementów w tablicy, mniejsza od 1000000 oraz $q$ – liczba, której będziemy szukać w tablicy. W drugim wierszu znajduje się $n$ liczb całkowitych oddzielonych spacjami – elementy tablicy $t ab$ .

Wyjście: Program powinien wypisać liczbę operacji wykonywanych przez algorytm wyszukiwania binarnego, potrzebną do znalezienia liczby $q$ w tablicy. Jeśli liczba $q$ nie znajduje się w tablicy, należy wypisać $- 1$ .

#include<iostream>
#include<algorithm> 
// dodajemy bibliotekę, w której znajduje się funkcja sort()
using namespace std;
int tab[1000000]; 
//deklarujemy tablice, do której będziemy wczytywać listę do 
//przeszukiwania zakładamy, że nie będzie ona miała więcej niż 
//1000000 elementów deklarujemy funkcje binsearcha o dwóch argumentach
//n - długość przeszukiwanej listy, q - szukana liczba
int binsearch(int n, int q) 
{
    int L = 0;
    int P = n - 1;
    int licznik = 0;
    //deklarujemy zmienne L i P, które będą zawierały indeksy końcowych 
    //elementów przedziału oraz licznik zliczający ilość iteracji
    while (L <= P) 
    {
        int M = (P+L) / 2;
        //deklarujemy zmienną M, która jest środkowym elementem 
        //przeszukiwanego fragmentu tablicy
        if (tab[M] == q) 
            return licznik; 
            // Jeśli znaleźliśmy szukany element, zwracamy 
            //wartość licznika
        else if (tab[M] < q) 
            L = M + 1;
            //jeśli szukana liczba jest większa od środkowej, 
            //przeszukujemy prawy przedział
        else 
            P = M - 1;
            //w przeciwnym przypadku przeszukujemy lewy przedział
        licznik++; //Zwiększamy licznik iteracji
    }
    return -1; 
    //Jeśli szukany element nie został znaleziony zwracamy -1
}

int main() 
{
    int n, q;
    cin >> n >> q;
    //wczytujemy ilość elementów tablicy oraz szukaną liczbę
    // Wczytujemy dane do tablicy
    for (int i = 0; i < n; i++)
        cin >> tab[i];
    sort(tab, tab + n); // Sortujemy tablicę
    // Wywolujemy funkcję wyszukiwania binarnego dla 
    //odpowiednich argumentów
    cout << binsearch(n, q);
}

Złożoność:

Złożoność czasowa algorytmu wynosi O(log2n), natomiast złożoność pamięciowa jest równa O(1).

Upper Bound:

Upper Bound wykorzystuje algorytm wyszukiwania binarnego, aby znaleźć pierwszy element w posortowanym zakresie, który jest większy od danej wartości.

Schemat działania algorytmu:

Dzielimy przedział: Algorytm zaczyna od badania środkowego elementu w tablicy. Jeśli wartość tego elementu jest mniejsza lub równa poszukiwanej wartości, algorytm wie, że szukana wartość musi znajdować się w drugiej połowie tablicy. W przeciwnym razie, jeśli wartość tego elementu jest większa od poszukiwanej wartości, algorytm wie, że szukana wartość może znajdować się w pierwszej połowie tablicy.
Powtarzamy: Proces ten jest powtarzany dla odpowiedniej połowy tablicy. Ten proces kontynuowany jest, aż pozostanie tylko jeden element w badanym przedziale.

Przykładowa implementacja:

#include <iostream>
#include <algorithm>
using namespace std;
int upperBound(int A[], int size, int val) 
{
    int left=0;
    int right=size; 
    while (left<right) 
    {
        int mid=left+(right-left)/2;
        if (A[mid]<=val) 
            left=mid+1; 
            // Jeśli wartość w środku jest mniejsza lub równa val,
            //przesuwamy lewą granicę
        else
            right=mid; 
            // W przeciwnym przypadku przesuwamy prawą granicę
    }
    return left;
}
int main() 
{
    int n;
    cin >>n; // Wczytanie liczby elementów do posortowania
    int A[n]; // Tworzymy tablicę
    int size = 0; 
    // deklarujemy zmienną na rozmiar aktualnie zapełnionej 
    //części tablicy
    for (int i = 0; i < n; i++) 
    {
        int x;
        cin >> x; // Wczytujemy kolejny element do posortowania
        int index = upperBound(A, size, x); 
        // szukamy indeksu pierwszego elementu większego od x
        if (index < size) 
            cout << A[index] << " "; 
            // Wypisujemy pierwszy element większy od x
        else
            A[size++] = x; 
            // Dodajemy x do zbioru A i zwiększamy rozmiar zapełnionej
            //części tablicy
    }
}

Złożoność:

Algorytm ten działa bardzo szybko, ponieważ przy każdym kroku eliminuje połowę tablicy jako potencjalną lokalizację poszukiwanej wartości. Jego złożoność czasowa wynosi O(log n).

Lower Bound:

Lower Bound w C++ wykorzystuje algorytm wyszukiwania binarnego, aby znaleźć pierwszy element w posortowanym zakresie, który nie jest mniejszy od danej wartości.

ZADANIE: Napisz funkcję Lower Bound, która będzie zwracała pierwszy element listy, który nie jest mniejszy od podanej wartości.