#include "pch.h"
#include <iostream>

using namespace std;
//Стандартний компаратор
template <typename T>
class standart_cmp
{
public:
  static bool less(const T &a, const T &b)
  {
    return a < b;
  }
};

//Функцiя злиття масиву
//array - масив, який впорядкований (за допомогою цього ж компаратора) до middle, i пiсля middle
//buffer - масив, розмiром не менше нiж array
template <typename T, typename cmp = standart_cmp<T> >

void merge(T *array, T *buffer, int left, int middle, int right)
{
  //iндеси зчитування чисел з array
  int it_left = 0;
  int it_right = 0;

  //Як тiльки будь - якої з "iтераторiв" виходить за кордон, припиняємо цикл
  while (left + it_left < middle && middle + it_right < right)
  {
    if (cmp::less(array[left + it_left], array[middle + it_right]))
    {
      buffer[it_left + it_right] = array[left + it_left];
      it_left++;
    }
    else
    {
      buffer[it_left + it_right] = array[middle + it_right];
      it_right++;
    }
  }

  //Записуємо частини, що залишилися, невиписанi з array
  while (left + it_left < middle)
  {
    buffer[it_left + it_right] = array[left + it_left];
    it_left++;
  }

  while (middle + it_right < right)
  {
    buffer[it_left + it_right] = array[middle + it_right];
    it_right++;
  }

  //Виписуємо buffer в array
  for (int i = 0; i < it_left + it_right; i++)
    array[left + i] = buffer[i];
}


// array - масив
// buffer - буфер для сортування, розмiром не менше, нiж array
// left - нижня межа, right - верхня
template <typename T, typename cmp = standart_cmp<T> >
void merge_sort(T *array, T *buffer, int left, int right)
{
  // Масив одиничного розмiру вже отсортiрованностi вважається
  if (right - left <= 1)
  {
    return;
  }

  // iндекс серединного елемента
  int middle = left + (right - left) / 2;



 // Сортуємо половинки масиву
  merge_sort(array, buffer, left, middle);
  merge_sort(array, buffer, middle, right);

// Складаємо з двох вiдсортованих половинок

 // Цiлий вiдсортований масив
  merge<T, cmp>(array, buffer, left, middle, right);
}
int binarySearch(int arr[], int l, int r, int x)
{
  while (l <= r) {

    int m = l + (r - l) / 2;

    // Перевірка x,y
    if (arr[m] == x)
      return m;

    // як що x совпада то ухилення
    if (arr[m] < x)
      l = m + 1;

    // як що х малий то ухилення правого руху
    else
      r = m - 1;
  }

  // описання елементу
  // не присутній
//
  return -1;
}



int main()
{
  setlocale(LC_CTYPE, "ukr");
  int n;
  cout << "Введiть скiльки елементiв вам потрiбно [1-256]" << endl;
  cin >> n;
  while (n < 1 || n>256) { //цикл для перевірки
    cout << "Повинно бути[1-256]\n";
    cin >> n;
  }



  int *arr = new int[n];
  int *buff = new int[n];



  for (int i = 0; i < n; i++)
  {
    cout << "Введiть елемент  " << endl;
    cin >> arr[i];
  }

  merge_sort(arr, buff, 0, n);

  cout << " Вiдсортованi числа способом злиття" << endl;
  for (int i = 0; i < n; i++)
  {
    cout << arr[i] << " ";
  }

  cout << endl;

  int n2; //друга частина програми пошуку
  cout << "Уведiть кiлькiсть елементiв для пошуку" << endl;


  cin >> n2; //введення розміру пошуку


  int *arrs = new int[n2]; //запис в масив
  for (int i = 0; i < n2; i++) //цикл для введення елементів



 {
    cout << "Введiть елемент  " << endl;
    cin >> arrs[i];
  }



  for (int i = 0; i < n2; i++)
  {

 int result = binarySearch(arr, 0, n - 1, arrs[i]);  //підрахунок та запис знайденних індексів

    if (result == -1) cout << "Елемент " << arrs[i] << " вiдсутнiй у вiдсортованному массивi" << endl;

 else cout << "Елемент " << arrs[i] << " знаходиться у вiдсортованному массивi за iндексом " << result << endl;

  }
  cout << endl;

  return 0;