//Szukanie z wartownikiem zadanego elementu w tablicy
//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.
// Przyjete zostalo zalozenie ze faktyczny rozmiar tablicy to size + 1.
template<typename T> int gsearch(const T& x, T* array, size_t size)
{
    // Aktualny indeks w tablicy wskazuje na pierwszy element
    size_t i = 0;
    // Inicjalizacja wartownika
    array[size] = x;
    
    // Powtarzaj dopoki element i jest rozny od x
    while (array[i] != x) ++i;
    
    // Zwroc indeks i gdy jest mniejszy od size, w przeciwnym wypadku -1
    return i < size ? i : -1;   
}

// Funkcja wyswietla tablice wskazna przez "array" o rozmiarze "size"
template<typename T> void printArray(const T* array, size_t size)
{
    // Dla kazdego elementu tablicy
    for (size_t i = 0; i < size; ++i)
    {
        // Wyswietl element i, gdy indeks elementu + 1 dzieli sie 
        // bez reszty przez 10, wstaw znak nowego wiersza,
        // w przeciwnym wypadku wstaw znak tabulacji.
        std::cout << array[i] << ((i + 1) % 10 == 0 ? "\n" : "\t");
    }
}

int main()
{
    // Liczba elementow tablicy
    const size_t size = 100;
    // Przydziel pamiec na size elementow + 1 na wartownika
    int *int_array = new int[size + 1];
    
    // Inicjalizacja ziarna generatora liczb pseudo-losowych
    srand(time(0));
    
    // Losowa inicjalizacja tablicy
    for (size_t i = 0; i < size; ++i)
    {
        // Wartosc losowa z przedzialu od 0 do 99
        int_array[i] = rand() % 100;
    }
    
    // Wyswietl tablice
    printArray(int_array, size);
    
    // Bedziemy szukac losowej wartosci z przedzialu od 0 do 99
    const int val = rand() % 100;
    // Znajdz wylosowana wartosc w tablicy    
    int index = gsearch(val, int_array, size);
    
    if (index < 0)
        std::cout << "Element o wartosci " << val << " nie zostal znaleziony" << std::endl;
    else
        std::cout << "Element o wartosci " << val << " zostal znaleziony na pozycji " << index << std::endl;
        
    // Zwolnij pamiec zajmowana przez tablice
    delete[] int_array;
    
    return EXIT_SUCCESS;
}