두 갈래 찾기

#include <iostream>

using namespace std;

int array[] = {1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4};
const int size = sizeof array / sizeof *array;

int binarySearchLeft(const int (&array)[size], int value)
{
	int left = 0;
	int right = size - 1;

	while (left < right)
	{
		int mid = left + (right - left) / 2;

		if (array[mid] >= value)
			right = mid;
		else
			left = mid + 1;
	}

	if (array[left] == value)
		return left;
	else
		return -1;
}

int binarySearchRight(const int (&array)[size], int value)
{
	int left = 0;
	int right = size - 1;

	while (left < right)
	{
		int mid = left + (right - left + 1) / 2;

		if (array[mid] > value)
			right = mid - 1;
		else
			left = mid;
	}

	if (array[left] == value)
		return left;
	else
		return -1;
}

int main()
{
	int left = binarySearchLeft(array, 2);
	cout << "left: " << left << endl;
	int right = binarySearchRight(array, 2);	
	cout << "right: " << right << endl;
}

int binarySearchLeft(int *array, int size, int value)
{
	if (array == NULL || size <= 0)
		return -1;

	int left = 0;
	int right = size - 1;

	while (left != right - 1 && left < right)
	{
		int mid = left + (right - left) / 2;

		if (array[mid] > value)
		{
			right = mid;
		}
		else
		if (array[mid] < value)
		{
			left = mid;
		}
		else
		{
			return mid;
		}
	}

	return left;
}

int binarySearchRight(int *array, int size, int value)
{
	if (array == NULL || size <= 0)
		return -1;

	int left = 0;
	int right = size - 1;

	while (left != right - 1 && left < right)
	{
		int mid = left + (right - left) / 2;

		if (array[mid] > value)
		{
			right = mid;
		}
		else
			if (array[mid] < value)
			{
				left = mid;
			}
			else
			{
				return mid;
			}
	}

	return right;
}