---

#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <utility>
#include <algorithm>
#include <random>
using namespace std;
void uniform_vector(vector<int>& arr, double min_val = 0, double max_val = 1000000)
{
 int n = arr.size();
 double step = (max_val - min_val) / (n - 1);

 for (int i = 0; i < n; i++)
 {
  arr[i] = static_cast<int>(min_val + step * i);
 }
}
void exp_vector(vector<int>& arr, double min_pow = 1, double max_pow = 6,
 double base = 10)
{
 int n = arr.size();
 double step = (max_pow - min_pow) / (n - 1);

 for (int i = 0; i < n; i++)
 {
  double exp = min_pow + step * i;
  arr[i] = static_cast<int>(pow(base, exp));
 }
}
pair<int, long> binary_search(const vector<int>& arr, int key)
{
 long op_counter = 0;
 int left = 0;
 int right = arr.size() - 1;

 while (left <= right)
 {
  int mid = left + (right - left) / 2;
  op_counter++;
  if (arr[mid] == key)
   return { mid, op_counter };
  else if (arr[mid] < key)
   left = mid + 1;
  else right = mid - 1;
 }
 return { -1, op_counter };
}
pair<int, long> interpolation_search(const vector<int>& arr, int key)
{
 long op_counter = 0;
 int left = 0;
 int right = arr.size() - 1;

 while (left <= right && key >= arr[left] && key <= arr[right])
 {
  op_counter += 2;
  if (arr[left] == arr[right])
  {
   op_counter++;
   if (arr[left] == key)
    return { left, op_counter };
   return { -1, op_counter };
  }

  int pos = left + (key - arr[left]) * (right - left) / (arr[right] - arr[left]);

  op_counter++;

  if (arr[pos] == key)
   return { pos, op_counter };
  else if (arr[pos] < key)
   left = pos + 1;
  else right = pos - 1;
 }
 return { -1, op_counter };
}

void add_to_file(const vector<double>& res, int n, ofstream& file)
{
 file << n << ";";
 for (int k = 0; k < res.size(); k++)
  file << int(res[k]) << ";";
 file << "\n";
}
int main()
{
 ofstream file("practice2.csv");
 file << "size;binary_search_lin;interpolation_search_lin;binary_search_exp;interpolation_search_exp\n"; 
  vector<int> lin_arr, exp_arr;
  random_device rd;
  mt19937 gen(rd());
  const int TEST_RUNS = 2000;
  for (int size = 2000; size <= 30000; size += 1000)
  {
   lin_arr.resize(size);
   exp_arr.resize(size);
   
   uniform_vector(lin_arr, 0, 1000000);
   exp_vector(exp_arr, 1, 6, 10);

   uniform_int_distribution<int> distrib(0, size - 1);
   long lin_bin_ops = 0, lin_int_ops = 0; 
   long exp_bin_ops = 0, exp_int_ops = 0;

   for (int t = 0; t < TEST_RUNS; t++)
   {
    int lin_indx = distrib(gen);
    int lin_key = lin_arr[lin_indx];

    auto lin_bin_srch = binary_search(lin_arr, lin_key);
    lin_bin_ops += lin_bin_srch.second;

    auto lin_inter_srch = interpolation_search(lin_arr, lin_key);
    lin_int_ops += lin_inter_srch.second;

    int exp_indx = distrib(gen);
    int exp_key = exp_arr[exp_indx];

    auto exp_bin_srch = binary_search(exp_arr, exp_key);
    exp_bin_ops += exp_bin_srch.second;

    auto exp_inter_srch = interpolation_search(exp_arr, exp_key);
    exp_int_ops += exp_inter_srch.second;
   }
   add_to_file({ double(lin_bin_ops) / TEST_RUNS,
   double(lin_int_ops) / TEST_RUNS, double(exp_bin_ops) / TEST_RUNS,
   double(exp_int_ops) / TEST_RUNS }, size, file);
  }
 file.close();
}