/* 
   Laboratorium Praktyki Programowania  
*/


/* Należ pozostawić definicję tylko jednej ze stałych : */

/* dla nowszych kompilatorów */
#define ANSI

/* dla starszych kompilatorów */
//#define ARM


#ifdef ANSI
#include <iostream>
#include <cstring>
#include <cassert>
#include <cstdlib>
using namespace std;
#endif

#ifdef ARM
#include <iostream.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#endif

// funkcja porownujaca dla qsort
// Tu uwaga: 
// Do sortowania bardziej elegancko byłoby wykorzystać nagłówek <algorithm>   

int porownaj(const void* x,const void* y);

class Tablica{
private: 
  int rozmiar;
  int *T;
public:
  Tablica(int n);
  ~Tablica();
  int wczytajElem(int);
  int wczytaj(int);    
  void wypisz();
  void sortuj(){qsort(T,rozmiar,sizeof(int),porownaj);}
  // szukania interpolacyjne
  int ls(int);
};


int main(){
  Tablica *t;
  int n,szuk,index;

  cout << "Ile liczb zamierzasz wprowadzic? ";
  cin >> n;
  t = new Tablica(n);
  t->wczytaj(n);

  // posortowanie wczytanego wektora funkcja biblioteczna qsort
  t->sortuj();
  cout << " T po posortowaniu " <<endl;
  t->wypisz();

  cout << " Podaj szukany element : ";
  cin >> szuk;
  index=t->ls(szuk);  
  if (index >=0)
    cout << szuk << " znajduje sie w tablicy na pozycji " << index << endl;
  else 
    cout << szuk << " nie ma takiego elementu!"<<endl;
  delete t;
  return 0;
}


// szukanie interpolacyjne
// zwraca indeks szukanego elementu lub -1, gdy go nie znajdzie
int Tablica::ls(int element){
  int left=0, right=rozmiar-1,nowy;
  double wsp;


  while ( T[right]!=T[left] ) {
    wsp=((double)(element-T[left]))/(T[right]-T[left]);
    if ( wsp<0 || wsp >1 )
      return -1;
    nowy=(int)(left+(right-left)*wsp);
    
    if ( T[nowy]==element )
      return nowy;
    else if ( T[nowy]<element ) 
      left=nowy+1;
    else
      right=nowy-1;
  }
  if ( T[right]==element )
    return right;
  else
    return -1;
}


Tablica::Tablica(int n){
  int i;
  rozmiar=n;T=new int[rozmiar];
  for(i=0;i<rozmiar;T[i++]=0); 
}

Tablica::~Tablica(){
  delete[] T;
}

int Tablica::wczytajElem(int n){
  assert(0<=n<rozmiar);
  cout << "Podaj liczbe "<< n+1 << " : ";
  cin >> T[n];
  return 0;
}

int Tablica::wczytaj(int n){
  int i;
  assert(0<=n<rozmiar);
  for(i=0;i<rozmiar;i++) wczytajElem(i); 
  return 0;
}

void Tablica::wypisz(){
  int i; 
  for (i=0 ; i<rozmiar ; i++)
    cout << T[i] << " ";
  cout << endl;
}

int porownaj(const void* x,const void* y){
  const int *ix=(const int*)x, *iy=(const int*)y;
  if ( *ix > *iy )
    return 1;
  else if ( *ix == *iy )
    return 0;
  else 
    return -1;
}