//Wyszukiwanie binarne
//www.algorytm.org

// Wymagane dla operacji wejscia/wyjscia
#include <iostream>

// Funkcja zwraca indeks poszukiwanego elementu "x" w tablicy wskazanej
// przez "array" o liczbie elementow "size", w przypadku gdy pasujacy
// element nie zostal odnaleziony, funkcja zwraca -1
template<typename T> int binSearch(const T& x, const T* array, size_t size)
{
    // Zainicjalizuj zmienne pomocnicze: lewy, prawy
    int l = 0, p = size - 1, s;
    // Powtarzaj dopoki l <= p    
    while (l <= p)
    {
        // Wyznacz srodek przedzialu
        s = (l + p) / 2;
        // Jezeli wartosc elementu o indeksie s jest rowna x to zwroc indeks
        if (array[s] == x)
            return s;
        // Jezeli wartosc elementu jest mniejsza, to przesun p na (srodek - 1)
        if (array[s] > x)
            p = s - 1;
        // Jezeli wartosc elementu jest wieksza to przesun l na (srodek + 1)            
        else
            l = s + 1;        
    }
    // Jezeli wartosc nie zostala znaleziona to zwroc -1    
    return -1;
}

int main()
{
    // Inicjalizacja stalej tablicy liczb calkowitych    
    const int int_array[] = {-5, -4, -3, -2, -1,  0,  1,  2,  3,  4,  5};
    
    // Wyszukaj wartosc 0,
    // liczba elementow tablicy to jej rozmiar / rozmiar elementu.        
    int index = binSearch(0, int_array, sizeof(int_array) / sizeof(int));
    
    if (index < 0)
        std::cout << "Element nie zostal znaleziony" << std::endl;
    else
        std::cout << "Element zostal znaleziony na pozycji " << index << std::endl;    
    
    // Poprawne zakonczenie programu
    return EXIT_SUCCESS;
}