#include <cstdlib>
#include <ctime>
#include <iostream>

using namespace std;

/**
   Znajduje element w uporządkowanej tablicy.
   @param a uporządkowana tablica z elementami do przeszukania
   @param from początek przeszukiwanego zakresu
   @param to koniec przeszukiwanego zakresu
   @param value wartość do wyszukania
   @return indeks pierwszego pasującego elementu albo -1 przy braku trafienia
*/
int binary_search(int a[], int from, int to, int value)
{
   if (from > to)
   {
      return -1;
   }

   int mid = (from + to) / 2;
   if (a[mid] == value)
   {
      return mid;
   }
   else if (a[mid] < value)
   {
      return binary_search(a, mid + 1, to, value);
   }
   else
   {
      return binary_search(a, from, mid - 1, value);
   }
}

int main()
{
   srand(time(0));
   const int SIZE = 20;
   int values[SIZE];
   values[0] = 0;
   for (int i = 1; i < SIZE; i++)
   {
      values[i] = values[i - 1] + rand() % 10;
      cout << values[i] << " ";
   }
   cout << endl;

   bool done = false;
   while (!done)
   {
      cout << "Wprowadź liczbę do wyszukania, -1 w celu zakończenia: ";
      int target;
      cin >> target;
      if (target == -1)
      {
         done = true;
      }
      else
      {
         int pos = binary_search(values, 0, SIZE - 1, target);
         cout << "Znaleziona na pozycji " << pos << endl;
      }
   }
   return 0;
}

