#include <iostream>
#include <ctime>
#include <windows.h>
#include <algorithm>
using namespace std;

void main()
{
	srand(time(0));
	rand();

	// array size
	const int size = 50000;

	// integer data array
	int ar[size];

	// fill array by random values
	for (int i = 0; i < size; i++)
	{
		ar[i] = rand() % 10000;
	}

	// print array - foreach example!
	for (int current : ar)
	{
		cout << current << ", ";
	}
	cout << "\n\n";

	// some value to find in array
	int value_to_find = 777;

	//////////////////////////////////////////////////////////////////
	// linear search
	//////////////////////////////////////////////////////////////////

	int linear_iteration_count = 0;
	int linear_index = -1;

	LARGE_INTEGER frequency, start_time, end_time;
	QueryPerformanceFrequency(&frequency);
	QueryPerformanceCounter(&start_time);

	for (int i = 0; i < size; i++)
	{
		linear_iteration_count++;
		if (ar[i] == value_to_find)
		{
			linear_index = i;
			break;
		}
	}

	QueryPerformanceCounter(&end_time);

	double work_time = (double)(end_time.QuadPart - start_time.QuadPart) / frequency.QuadPart * 1000.0;

	cout << "\nValue was find by index: " << linear_index << "\n";
	cout << "Linear iteration count: " << linear_iteration_count << "\n";
	cout << "Linear search work time: " << work_time << "ms." << "\n";
	cout << "\n////////////////////////////////////////\n";

	system("pause");

	//////////////////////////////////////////////////////////////////
	// binary search
	//////////////////////////////////////////////////////////////////

	int binary_iteration_count = 0;
	int binary_index = -1;

	sort(ar, ar + size);

	// print sorted array
	for (int i = 0; i < size; i++)
	{
		cout << /*i << " - " << */ar[i] << ", ";
	}

	QueryPerformanceFrequency(&frequency);
	QueryPerformanceCounter(&start_time);

	int L = 0, R = size - 1; // left and right border
	int M; // median element index
	while (true)
	{
		binary_iteration_count++;
		M = L + (R - L) / 2; // or (L + R) / 2
		if (ar[M] > value_to_find)
			R = M - 1;
		else if (ar[M] < value_to_find)
			L = M + 1;
		else
		{
			binary_index = M;
			break;
		}
		if (L > R)
			break; // oops!
	}

	QueryPerformanceCounter(&end_time);

	work_time = (double)(end_time.QuadPart - start_time.QuadPart) / frequency.QuadPart * 1000.0;

	cout << "\nValue was find by index: " << binary_index << "\n";
	cout << "Binary Iteration count: " << binary_iteration_count << "\n";
	cout << "Binary search work time: " << work_time << "ms.\n";

	system("pause");
}