순차 탐색 (Sequential Search)

// 배열 arr에 x가 몇 번 나오는지 반환
int Count(const int* const arr, const int n, const int x)
{
	// TODO:
	int count = 0;

	for (int i = 0; i < n; i++)
	{
		if (arr[i] == x)
		{
			count++;
		}
	}

	return count;
}

// 배열 arr에 x가 있으면 index 반환, 없으면 -1 반환
int SequentialSearch(int* arr, int n, int x)
{
	// TODO:
	for (int i = 0; i < n; i++)
	{
		if (arr[i] == x)
		{
			return i;
		}
	}

	return -1;
}

int SortedCountHelper(int* arr, int n, int x, int start)
{ 
	int count = 0;
	for (int i = start; i < n; i++)
	{
		if (arr[i] == x)
		{
			count++;
		}
		else
			break;
	}

	return count;
}

// 만약 arr가 이미 오름차순으로 정렬된 배열이라면,
int SortedCount(int* arr, int n, int x)
{
	int i = SequentialSearch(arr, n, x);

	if (i >= 0)
		return SortedCountHelper(arr, n, x, i + 1) + 1;
	else
		return 0;
}