This was the solution to an interview question that I did. The goal is to return the number that occurs the majority of the time in a sorted array if there is one. I fixed the minor issue with the binary search function and am uploading this for anyone interested. This was the first time I have implemented a binary search so I'm not too upset ab…

PopularNumber.cpp

#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
#include <optional>


#define AT_SUBMISSION false
#define AFTER_SUBMISSION true

// Set the below to AT_SUBMISSION or AFTER_SUBMISSION to see what I've done
#define VIEW_VERSION AFTER_SUBMISSION



// Integer that occupies more than half of the array

using Sorted = std::vector<int>;

auto binary_search(const Sorted& _numbers, int _val)
{
	auto _begin = _numbers.begin();
	auto _end = _numbers.end();
	auto _half = _begin;

	while(_end - _begin > 1)
	{
		_half = _begin + ((_end - _begin) / 2);
#if VIEW_VERSION == AT_SUBMISSION
		if (*_half > _val)
		{
			_end = _half;
		}
		else
		{
			_begin = _half;
		};
#else
		if (*_half < _val)
		{
			_begin = _half;
		}
		else
		{
			_end = _half;
		};
#endif
	};
	return _begin;
};

/**
 * @brief 
 * @param _numbers 
 * @return 
*/
static std::optional<int> popular_number(const Sorted& _numbers)
{
	auto _halfSize = _numbers.size() / 2;
	auto _center = _numbers.begin() + _halfSize;
	if ((_numbers.size() % 2) == 0)
	{
		++_center;
	};

	auto _first = binary_search(_numbers, *_center);
	if (*(_first + _halfSize) == *_center)
	{
		return *_center;
	}
	else
	{
		return std::nullopt;
	};
};

int main()
{	
	// 1 2 2 2 3
	// 1 1 2 2
	// 1 2 3 3
	// 2 2 2 3 4

	/*
		Everything after this point was added after submission but I'll leave it in case you want to run the "tests"
		The 1 1 2 2 input doesnt work still, but could be accounted for with a fix to the binary search implementation
	*/

	{
		Sorted _ivec{ 1, 2, 2, 2, 3 };
		if (popular_number(_ivec).value() != 2)
		{
			std::terminate();
		};
	};

	{
		Sorted _ivec{ 2, 2, 2, 3, 4 };
		if (popular_number(_ivec).value() != 2)
		{
			std::terminate();
		};
	};

	{
		Sorted _ivec{ 1, 2, 3, 3, 3 };
		if (popular_number(_ivec).value() != 3)
		{
			std::terminate();
		};
	};

	{
		Sorted _ivec{ 1, 2, 3, 4, 4 };
		if (popular_number(_ivec).has_value())
		{
			std::terminate();
		};
	};

	return 0;
};