#include <locale.h>
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <Windows.h>

using namespace std;

void ReadF(int *mas, int n) // читаем массив из файла, выводим на экран
{
	ifstream input; // объявление переменной input файлового типа для чтения из файла
	input.open("input.txt", ios::in);
	cout << "Исходный массив: \n";
	for (int i = 0; i < n; i++)
	{
		input >> mas[i]; // читаем
		cout << setw(3) << mas[i];
	}
	cout << "\n";
}


void WriteF(int *mas, int n) // записываем в файл
{
	ofstream output;
	output.open("output.txt", ios::app);
	cout << "Размер массива: " << n << "\n";
	for (int i = 0; i < n; i++)
		output << setw(3) << mas[i];
	for (int i = 0; i < n; i++)
		cout << setw(3) << mas[i];
	output << "\n";
	cout << "\n";
}

int DeleteOdd(int *mas, int n) // удаляем нечетные элементы
{
	ofstream output;
	output.open("output.txt", ios::app); // запись в конец файла
	int i, j, k = 0;
	for (i = 0; i < n; i++){
		if (mas[i] % 2 != 0)
		{
			k++;
			for (j = i; j < n-1; j++){
				mas[j] = mas[j + 1];
			}
			i--;
		}

	}
	cout << "\n";
	cout << "Количество нечетных элементов: " << k << "\n";
	n -= k;
	WriteF(mas, n);
	cout << "\n";
	return n;
}

int Insert(int *mas, int n, int k) // вставка N после элементов, равных К
{
	ofstream output;
	output.open("output.txt", ios::app);
	int i;
	for (i = 0; i <= n; i++)
	{
		if (mas[i] == k)
		{
			n++;
			for (int j = n; j > i; j--)
				mas[j] = mas[j - 1];
			mas[i + 1] = n; // вставка N
			i++; // обход нового элемента
		}
	}
	WriteF(mas, n);
	cout << "\n";
	return n;
}

void Transform(int *mas, int n)
{
	ofstream output;
	output.open("output.txt", ios::app);
	int buf, i = 0, j = n - 1;
	while (i <= j)
	{
		while (mas[i] >= 0) i++;
		while (mas[j] < 0) j--;
		if (i < j)
		{
			buf = mas[i];
			mas[i] = mas[j];
			mas[j] = buf;
			i++;
			j--;
		}
	}
	WriteF(mas, n);
	cout << "\n";
}

void LinearSearch(int *mas, int n) // линейный последовательный поиск
{
	ofstream output;
	output.open("output.txt", ios::app);
	int i = 1, key, sr = 0;
	bool k = false;
	cout << "Введите число, которое нужно найти в массиве: \n";
	cin >> key;
	while (k == false)
	{
		if (mas[i] == key) k = true;
		i++;
		sr++;
	}
	if (k)
	{
		cout << "Элемент " << key << " найден. Его номер = " << i - 1 << "\n";
		output << "Элемент " << key << " найден. Его номер = " << i - 1 << "\n";
	}
	else
	{
		cout << "Элемент не найден. \n";
		output << "Элемент не найден. \n";
	}
	cout << "Кол-во сравнений = " << sr << "\n";
	output << "Кол-во сравнений = " << sr << "\n";
}

void Sort(int *mas, int n)
{
	ofstream output;
	output.open("output.txt", ios::app);
	for (int i = 1; i <= n; i++)
	for (int j = n - 1; j >= i; j--)
	if (mas[j] < mas[j - 1])
	{
		int buf = mas[j];
		mas[j] = mas[j - 1];
		mas[j - 1] = buf;
	}
	WriteF(mas, n);
	cout << "\n";
}

void BinarySearch(int *mas, int n) // дихотомический (бинарный) поиск
{
	ofstream output;
	output.open("output.txt", ios::app);
	int l = 0, r = n - 1, s, sr = 0, key, nomer = 1;
	bool k = false;
	cout << "Введите число, которое нужно найти в массиве: \n";
	cin >> key;
	for (int i = 0; i <= n; i++)
	if (mas[i] < key) nomer++;

	do
	{
		s = (l + r) / 2; // средний элемент
		if (mas[s] < key) l = s + 1; // перенести левую границу
		else r = s; // перенести правую границу
		sr++;
	} while (l != r);
	if (mas[l] == key)
	{
		cout << "Элемент " << key << " найден. Его номер = " << nomer - 1 << "\n";
		output << "Элемент " << key << " найден. Его номер = " << nomer - 1 << "\n";
	}
	else
	{
		cout << "Элемент не найден. \n";
		output << "Элемент не найден. \n";
	}
	cout << "Кол-во сравнений = " << sr << "\n";
	output << "Кол-во сравнений = " << sr << "\n";
	cout << "\n";
}

void main()
{
	setlocale(LC_ALL, "rus");
	ifstream F; // объявление переменной input файлового типа для чтения из файла
	ofstream f; // для записи в файл
	f.open("output.txt", ios::out);
	int a = 0, number, K;

	cout << "Введите кол-во элементов в массиве: \n";
	cin >> number;
	cout << "\n";

	int *array = new int[number-1]; // выделили в динамической памяти место под массив из number элементов
	F.open("input.txt", ios::in);

	cout << "I. ЧТЕНИЕ. \n";
	ReadF(array, number);
	cout << "\n";

	cout << "II. ЗАПИСЬ В ФАЙЛ. \n";
	WriteF(array, number);
	cout << "\n";

	cout << "III. УДАЛЕНИЕ. ";
	number = DeleteOdd(array, number);

	cout << "IV. ВСТАВКА. \n";
	cout << "Введите число, после которого нужно вставить N: \n";
	cin >> K;
	number = Insert(array, number, K);

	cout << "V. ПЕРЕСТАНОВКА. \n";
	Transform(array, number);

	cout << "VI. ПОИСК ЭЛ-ТА В НЕОТСОРТИРОВАННОМ МАССИВЕ. \n";
	LinearSearch(array, number);
	cout << "\n";

	cout << "VII. ПРОСТОЙ ОБМЕН ПО ВОЗРАСТАНИЮ. \n";
	Sort(array, number);

	cout << "VIII. ПОИСК ЭЛ-ТА В ОТСОРТИРОВАННОМ МАССИВЕ. \n";
	BinarySearch(array, number);
	cout << "\n";


	F.close();
	f.close();
}