// PAIP IC1 10B LAB05
// LUKASZ KOLER
// lkoler@wi.zut.edu.pl

#define MAX 100
#include <iostream>
#include <string>
#include <cstdlib>
#include <time.h>
#include <iomanip>
#include <stdio.h>
using namespace std;

int Search_nat (int N, int A[],  int x)
{
    cout<<endl<<"Wyszukiwanie naturalne:"<<endl;
    int licznik=0;
for(int i = 0; i <= N; i++)
 {
 licznik++;
 if(x == A[i]){
      cout<<"Liczba "<<x<<" zostala znaleziona na pozycji: "<<i+1;
      cout<<endl<<"Licznik iteracji: "<<licznik;
      return(i);
      };
 if(x < A[i]){
      cout<<"Liczba nie znajduje sie w tablicy";
      return(0); //brak element x w tablicy A[]
      };
 }
return(0);
}

int Search_bin(int l, int p, int x, int A[])
{
  cout<<endl<<"Wyszukiwanie binarne:"<<endl;
  int sr;
  int licznik=0;

if (x < A[0]) { cout<<"Liczba "<<x<<" nie znajduje sie w tablicy"<<endl<<"Licznik iteracji: "<<licznik; return(0); }
if (x > A[MAX-1]) { cout<<"Liczba "<<x<<" nie znajduje sie w tablicy"<<endl<<"Licznik iteracji: "<<licznik; return(0); }
if (x == A[0]) { cout<<"Liczba "<<x<<" znajduje sie na pozycji: 0"<<endl<<"Licznik iteracji: "<<licznik; return(0); }
if (x == A[MAX-1]) { cout<<"Liczba "<<x<<" znajduje sie na pozycji: "<<MAX<<endl<<"Licznik iteracji: "<<licznik; return(0);}

  while(l<=p)
  {
    licznik++;
    sr = (l + p)/2;

    if(A[sr] == x){
      cout<<"Liczba "<<x<<" znajduje sie w tablicy na pozycji: "<<sr+1;
      cout<<endl<<"Licznik iteracji: "<<licznik;
      return(0);
      }

    if(A[sr] > x)
      p = sr - 1;
    else
      l = sr + 1;
}

  return -1; //zwracamy -1, gdy nie znajdziemy elementu
}

int main() {
    int tab[MAX];
    srand(time(NULL));
    int b = 0;
    int metoda;
    int trafione = 0;
    int tPozycja = 0;
    int lPorownania = 0;
    int lZamiany = 0;
    int x = MAX;

    // TABLICA LOSOWA
    for(int i=0;i<MAX;i++){
             tab[i] = rand()%(4*MAX-1)+0;
    }



    /* od MIN do MAX
    for(int i=0;i<MAX;i++){
             tab[i] = i;
             //tab[i] = rand()%(4*MAX-1)+0;
    }
    */

    /* od MAX do MIN
    for(int i=0;i<MAX;i++){
             tab[i] = x;
             x--;
    }
    */

    /*
    // WYSWIETLANIE TABLICY LOSOWEJ
    for(int i=0;i<MAX;i++){
            cout<<left<<setw(10)<<tab[i];
            if((i+1)%5==0)
            cout<<endl;
    }
    */

     // SORTOWANIE BĄBELKOWE

    for(int i=0; i<MAX-1; i++)
        for(int j=0; j<MAX-1-i; j++)
        {
            lPorownania=lPorownania+1;
                if(tab[j] > tab[j+1])
                {
                    swap(tab[j], tab[j+1]);
                    lZamiany=lZamiany+1;
                }
        }

// WYSWIETLANIE POSORTOWANEJ TABLICY

    cout<<"Sortowanie tablicy algorytmem babelkowym od najmniejszej do najwiekszej: "<<endl;

    for(int i=0; i<MAX; i++)
        cout <<setw(5)<<tab[i];
            cout<<endl<<endl;
/*
// WYSWIETLANIE ODWROTNIE POSORTOWANEJ TABLICY

   cout<<"Sortowanie tablicy algorytmem babelkowym od najwiekszej do najmniejszej: "<<endl;

    for(int i=MAX-1; i>0; i--)
         cout<<setw(5)<<tab[i];
              cout<<endl<<endl;
 */

    cout<<endl<<endl<<"Wpisz liczbe do sprawdzenia: "<<endl<<endl;
    cin>>b;

    cout<<endl<<"Wybierz metode wyszukiwania:"<<endl<<"1 - naturalne"<<endl<<"2 - binarne"<<endl;

    cin>>metoda;

    if(metoda == 1)
    Search_nat(MAX,tab,b);

    if(metoda == 2)
    Search_bin (0, MAX,  b, tab);

    /*
    for(int i=0;i<MAX;i++){
                    if(tab[i] == b) {
                    tPozycja = i;
                    trafione++;
                    }
     }

     if(trafione>0) {
     cout<<"Liczba, ktora podales ("<<b<<") znajduje sie w tablicy.";
     cout<<endl<<"Numer pozycji: "<<tPozycja<<endl<<endl<<endl;
     }
     else
     cout<<"Liczba, ktora podales ("<<b<<") NIE znajduje sie w tablicy."<<endl<<endl;
     */

//cout<<"Liczba wykonanych operacji porownania elementow: "<<lPorownania;
//cout<<endl<<"Liczba wykonanych zamian miejscami elementow: "<<lZamiany;


cout<<endl<<endl<<endl;
system("pause");
return 0;
}