Wyszukiwanie binarne (Binary Search)

Warunek konieczny:

Tablica MUSI BYĆ POSORTOWANA! Próba wykonania wyszukiwania binarnego na nieposortowanych danych da błędny wynik.

Algorytm:

1. Oblicz indeks środkowego elementu: mid = (lewy + prawy) / 2.
2. Jeśli tab[mid] == szukana, znaleziono element.
3. Jeśli tab[mid] > szukana, szukaj w lewej połowie (prawy = mid - 1).
4. Jeśli tab[mid] < szukana, szukaj w prawej połowie (lewy = mid + 1).

int binarySearch(int tab[], int n, int szukana) {
    int lewy = 0, prawy = n - 1;
    while (lewy <= prawy) {
        int mid = lewy + (prawy - lewy) / 2;
        if (tab[mid] == szukana) return mid;
        if (tab[mid] < szukana) lewy = mid + 1;
        else prawy = mid - 1;
    }
    return -1; // brak elementu
}

Złożoność:

• Złożoność czasowa: O(log n) (np. w tablicy 1 000 000 elementów wystarczy maksymalnie 20 porównań!).
• Wyszukiwanie liniowe (dla porównania): wymaga O(n) porównań.