//задан отсортированный по неубыванию массив целых чисел, вывести на экран номер элемента
//с заданным ключом или информацию о том, что такого элемента в масиве нет, поиск вести указанным методом.

#include "pch.h"
#include <iostream>
using namespace std;
void SortShell(int [], int );
int search(int[], int, int);

int main()
{
	setlocale(LC_ALL, "ru");
	int n;
	cout << "Введите количество элементов массива : ";
	cin >> n;
	int *a = new int[n];
	cout << "Введите элементы массива : ";
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	SortShell(a, n);
	for (int i = 0; i < n; i++) {
		cout << "     " << a[i];
	}
	cout << endl;
	int k;
	cout << "Введите ключ : ";
	cin >> k;
	if (search(a, n - 1, k) != -1) {
		cout << "позиция : " << search(a, n - 1, k) + 1 << " - й элементы." << endl;
	}
	else cout << "Данный элемент не был обнаружен в массиве." << endl;
	delete[] a;
	return 0;
}
void SortShell(int a[], int n) {
	int step = n / 2;

	while (step != 0) {

		for (int i = step; i < n; ++i) {
			int tmp = a[i];
			int j;
			int t;
			t = a[i];
			for (j = i - step; j >= 0 && a[j] > tmp; j = j - step)

				a[j + step] = a[j];

			a[j + step] = t;
		}
		step /= 2;
	}
}
//int search(int a[], int n, int x) {
//	a[n + 1] = x;
//	int i = 0;
//	while (a[i] != x) i++;
//	if (i == n + 1) return -1;
//	else return i;
//}
int search(int a[], int n, int x) {
	for (int i = 0; i < n; i++) {
		if (a[i] == x) return i;
	}
	return -1;
}