C++ Searching: Binary and Linear Implemented by James Pate Williams, Jr.

#pragma once

// Binary searches from the following website
// https://www.geeksforgeeks.org/binary-search/

typedef long long ll;

class Search
{
public:
	int IterativeBinarySearch(
		ll A[], ll x, int low, int high);
	int RecursiveBinarySearch(
		ll A[], ll x, int low, int high);
	int IterativeLinearSearch(
		ll A[], ll x, int low, int high);
};

#include "Search.h"

int Search::IterativeBinarySearch(
	ll A[], ll x, int low, int high)
{
	do
	{
		int middle = low + (high - low) / 2;

		if (x == A[middle])
			return middle;

		else if (x > A[middle])
			low = middle + 1;

		else if (x < A[middle])
			high = middle - 1;

	} while (high >= low);

	return -1;
}

int Search::RecursiveBinarySearch(
	ll A[], ll x, int low, int high)
{
	if (high >= low)
	{
		int middle = low + (high - low) / 2;

		if (x == A[middle])
			return middle;

		else if (x > A[middle])
			return RecursiveBinarySearch(
				A, x, middle + 1, high);

		else if (x < A[middle])
			return RecursiveBinarySearch(
				A, x, low, middle - 1);
	}
	
	return -1;
}

int Search::IterativeLinearSearch(
	ll A[], ll x, int low, int high)
{
	for (int i = low; i <= high; i++)
		if (x == A[i])
			return i;

	return -1;
}

// Searching.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include "Search.h"
#include <chrono>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
using chrono::duration_cast;
using chrono::nanoseconds;

ll A[1000001];

ll RandomLongLong()
{
	ll lo = rand();
	ll hi = rand();

	return (lo << 31) | hi;
}

void GenerateArray(ll A[], int n, int seed)
{
	for (int i = 1; i <= n; i++)
		A[i] = RandomLongLong();
}

void GenerateArrayMod(ll A[], int n, int mod, int seed)
{
	Search search;

	for (int i = 1; i <= n; i++)
	{
		while (true)
		{
			ll Ai = RandomLongLong() % mod;

			if (search.IterativeLinearSearch(
				A, Ai, 1, i) == -1)
			{
				A[i] = Ai;
				break;
			}
		}
	}
}

int Partition(ll* A, int p, int r)
{
	int q = p;
	ll t;

	for (int u = p; u <= r - 1; u++)
	{
		if (A[u] <= A[r])
		{
			t = A[q];
			A[q] = A[u];
			A[u] = t;
			q++;
		}
	}

	t = A[q];
	A[q] = A[r];
	A[r] = t;

	return q;
}

void RunQuickSort(ll* A, int p, int r)
{
	if (p < r)
	{
		int q = Partition(A, p, r);

		RunQuickSort(A, p, q - 1);
		RunQuickSort(A, q + 1, r);
	}
}

void RunSearches(
	Search search,
	ll A[],
	int n, int seed)
{
	int index[4];
	ll x = RandomLongLong() % n;

	GenerateArrayMod(A, n, 2LL * n, seed);
	RunQuickSort(A, 1, n);
	
	cout << "key = " << x << endl;

	if (n <= 25)
	{		for (int i = 1; i <= n; i++)
			cout << A[i] << " ";

		cout << endl;
	}

	cout << "Runtimes in nanoseconds" << endl;
	cout << "n" << "\t" << "Iter" << "\t";
	cout << "Recur" << "\t" << "Linear" << endl;
	cout << setw(5) << n << "\t";

	auto start1 = chrono::steady_clock::now();
	index[0] = search.IterativeBinarySearch(A, x, 1, n);
	auto final1 = chrono::steady_clock::now();

	cout << setw(5) << duration_cast<nanoseconds>(final1 - start1).count();
	cout << "\t";

	auto start2 = chrono::steady_clock::now();
	index[1] = search.RecursiveBinarySearch(A, x, 1, n);
	auto final2 = chrono::steady_clock::now();

	cout << setw(5) << duration_cast<nanoseconds>(final2 - start2).count();
	cout << "\t";

	auto start3 = chrono::steady_clock::now();
	index[2] = search.IterativeLinearSearch(A, x, 1, n);
	auto final3 = chrono::steady_clock::now();

	cout << setw(5) << duration_cast<nanoseconds>(final3 - start3).count();
	cout << endl;
	cout << "Search indicies" << endl;

	for (int i = 0; i < 3; i++)
		cout << "index[" << i << "] = " << index[i] << endl;
}

int main()
{
	cout << "Comparison of Iterative Binary Search," << endl;
	cout << "Recursive Binary Search, and Linear Search" << endl;

	while (true)
	{
		int n, seed;
		Search search;

		cout << "n = ";
		cin >> n;
		
		if (n == 0)
			break;

		cout << "seed = ";
		cin >> seed;
		srand(seed);

		RunSearches(search, A, n, seed);
	}
}