Wyszukiwanie binarne

Wyszukiwanie w tablicy w czasie O(n) jest dobre, ale można je dodatkowo zoptymalizować do O(log n), używając metody zwanej wyszukiwaniem binarnym. 

Warunek stosowania wyszukiwania binarnego: Elementy tablicy muszą być posortowane w kolejności rosnącej albo malejącej.

Na przykład, 

int Arr[]={1,2,3,4,5};
int Brr[]={5,3,9,6,7};

W tablicy Arr możemy zastosować wyszukiwanie binarne, aby znaleźć element, ponieważ wszystkie elementy tablicy Arr są posortowane w kolejności rosnącej.

Nie możemy zastosować wyszukiwania binarnego w tablicy Brr, ponieważ jej elementy są losowe.

Podstawowa logika

Sprawdź dokładnie środkowy element tablicy, 

1. Jeśli jest równy szukanemu elementowi, wypisz go,
2.  jeśli jest mniejszy od szukanego elementu, przeszukaj prawą część pozostałej tablicy, 
3.  jeśli jest większy, przeszukaj lewą część pozostałej tablicy.

Powtarzaj ten proces, aż znajdziesz szukany element; w przeciwnym razie zwróć -1.

Szczegółowy proces

1. Najpierw inicjalizujemy 2 zmienne wskazujące początek i koniec tablicy. Następnie używamy pętli while z warunkiem, że początek zawsze musi być mniejszy lub równy końcowi.

    int s=0; //początek
    int e=n; //koniec
    
    while(s<=e){
    
    }

2. Znajdź środkowy element, obliczając (s+e)/2. Jeśli mid jest dokładnie równy szukanemu elementowi, zwróć go.

    int s=0; //początek
    int e=n; //koniec
    
    while(s<=e){
    
        int mid=(s+e)/2;  //Środek tablicy

        if(arr[mid]==key){   //jeśli jest równy, zwróć go
            return mid;
        }
    
    }

3. Jeśli środkowy element jest większy od szukanego elementu, oznacza to, że szukany element musi znajdować się po lewej stronie tablicy. Dlatego przesuwamy koniec tablicy na mid-1. Teraz mamy tablicę o rozmiarze n/2 i powtarzamy ten proces.

    int s=0; //początek
    int e=n; //koniec
    
    while(s<=e){
    
        int mid=(s+e)/2;  //Środek tablicy

        if(arr[mid]==key){
            return mid;
        }
        else if(arr[mid]>key){
            e=mid-1;         //Przesuń koniec na mid-1
        }
    
    }

4. Jeśli żaden z tych warunków nie jest spełniony, oznacza to, że element musi być większy od środkowego elementu. W takim przypadku przeszukujemy prawą część tablicy i przesuwamy jej początek na pozycję mid+1.

    int s=0;
    int e=n;
    while(s<=e){
        int mid=(s+e)/2;

        if(arr[mid]==key){
            return mid;
        }
        else if(arr[mid]>key){
            e=mid-1;
        }
        else{
            s=mid+1;   //Przesuń początek na mid+1
        }
    }

Wykonujemy program, aż znajdziemy element. Jeśli element nie występuje w tablicy, zwracamy -1.

Złożoność czasowa

Na każdym kroku liczba elementów zmniejsza się o połowę. Oznacza to, że czas wykonania każdego kroku jest o połowę krótszy niż poprzedniego. Czas zmniejsza się więc logarytmicznie, co daje złożoność czasową wyszukiwania binarnego równą O(log n).