#include <string>
#include <ctime>
template <class T>
bool sequential_search(T *p, int size,T key, int (*f)(T a, T b), int & pos)
{
	for (int i = 0 ; i < size; i++)
	{
		if (f(p[i], key)==0)
		{
			pos = i;
			return true;
		}
	}
	return false;
};
template <class T>
bool binary_search (T *p, int size, T key, int(*f)(T a, T b), int &pos)
{
	bubble_sort(p, size);
	print(p, size);
	int begin=0, end = size - 1;
	while (begin <= end)
	{
			int med = (end + begin)/2;
		if (f(key, p[med])>0)// если число лежит правее med, то оно больше, и теперь рассматриваем массив с начальным элементом p[med]
			begin = med+1;
		else if(f(key, p[med])<0)// если число лежит левее med, то оно меньше, и теперь рассматриваем массив с последним элементом p[med]
			end = med-1;
		else if (f(key,p[med])==0)
		{
			pos = med;// если med равняется искомому числу, задача выполнена
			return true;
		}
	}
	return false;
}
template <class T>
int comp_int(T a, T b)
{
	if (a>b)
		return 1;
	else if(a<b)
		return -1;
	else if(a==b)
		return 0;
}
struct student
{
	char *Name;
	int group;
	int tel;
	char *mw;
	char *birthday;

	student()// структура
	{
		Name = NULL;
		group = 0;
		tel = 0;
		mw = "-";
		birthday = NULL;
	}
};
int student_comp(student A, student B)
{
	return strcmp(A.Name, B.Name);
};
int char_cmp(const char* str1, const char* str2)
{
	return strcmp(str1, str2);
}
void print(student St)
{
	printf("Name:\t %s\n", St.Name);
	printf("Group:\t %d\n", St.group);
	printf("Telephone:\t %d\n", St.tel);
	printf("Pol:\t %c\n", St.mw);
	printf("Birthday:\t %s\n", St.birthday);
}
int *rand_int(int N)
{
	srand((unsigned)time(NULL));
	int *p = new int[N];
	for(int i = 0; i < N; i++)
		p[i] = rand()%99+1;
	return p;
}
double *rand_double(int N)
{
	srand((unsigned)time(NULL));
	double *p = new double[N];
	for(int i = 0; i < N; i++)
		p[i] = rand()%99+1;
	return p;
}
template <class T>
void print(T *p, int N)
{
	for(int i = 0; i < N; i++)
		cout << p[i] << " ";
	cout << endl;
}
template <class T>
void bubble_sort(T *p, int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 1; j < n-i; j++)
		{
			if(p[j-1]>p[j])
			{
				T tmp = p[j];
				p[j]=p[j-1];
				p[j-1]=tmp;
			}
		}
	}
}
template <class T>
int interpolation_search(T* p ,int n, T key)
{
	bubble_sort(p, n);
	print(p, n);
	  int low = 0;
  int high = n - 1;
  int med;
  while (p[low] <= key && p[high] >= key)
  {
   med = low + ((key - p[low]) * (high - low)) / (p[high] - p[low]); // вычисление следующей пробы
   if (p[med] < key) low = med + 1; // проверяем, как соотносится ключ с элементами этого интервала
   else if (p[med] > key) high = med - 1;
        else return med;
  }
  if (p[low] == key) return low; // после того, как вышли из цикла, проверяем, является ли нижняя граница последнего интервала ключом
  else return -1;
 }