/* 
   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



// szukania interpolacyjne
int ls(int *,int,int);

// funkcja porownujaca dla qsort
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;
}

int main(){
  int *T,n;
  int i, szuk,index;

  cout << "Ile liczb zamierzasz wprowadzic? ";
  cin >> n;

  T = new int[n];

  for ( i=0; i<n ; i++ ){
    cout << "Podaj liczbe "<< i+1 << " : ";
    cin >> T[i];
  }

  // posortowanie wczytanego wektora funkcja biblioteczna qsort
  qsort(T,n,sizeof(int),porownaj);

  cout << " T po posortowaniu " <<endl;
  for (i=0 ; i<n ; i++ )
    cout << T[i] << " ";
  cout << endl;
  
  cout << " Podaj szukany element : ";
  cin >> szuk;

  index=ls(T,n,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 ls(int t[],int size,int element){
  int left=0, right=size-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;
}