#include <iostream>
#include <iomanip>
#include <fstream>
long long BinSearch(const int* arr, int count, int key);
using namespace std;

int main()
{

	int *array;
	int key;
	long long result;//добавить бинарный поиск и оставить интерполирующий
	fstream in("in1.txt", fstream::in);
	if (!in)
		return 0;
	int num1;
	int num;
	in >> num1;
	array = new int[num1];
	int i = 0;
	while (!in.eof()) {
		in >> num;
		array[i] = num;
		i++;
	}
	cout << "Enter a key of search: ";
	cin >> key;
	result = BinSearch(array, i, key);
	int result1 = array[result];
	if (result != -1 )
	{
		for (int g = result; g < num1; g++)
		{
			if (array[g]>result1)
			{
				cout <<"next element "<< array[g] << " "<<endl;
				break;
			}
		}
	}

	else
	{
		for (int g = 0; g < num; g++)
		{

			if (array[g] > key)
			{
				cout << "next element " << array[g] << " " << endl;
				break;
			}
		}
	}
	if (result != -1)
		cout << "Value is found in an element with an index " << result << endl;
	else
		//значение не найдено
		cout << "Value is not found" << endl;
	system("pause");
	return 0;
}

long long BinSearch(const int* arr, int count, int key)
{
	int l = 0;            // нижняя граница
	int u = count - 1;    // верхняя граница

	while (l <= u) {
		long long m = (l + u) / 2;
		if (arr[m] == key) return m;
		if (arr[m] < key) l = m + 1;
		if (arr[m] > key) u = m - 1;
	}
	return -1;
}