풀이전략

1) 오름차순이고
2) 시간 복잡도는 LogN이므로
-> 이진탐색이다.

• 힌트를 참고함. : 타겟 발견시 처음 인덱스와 마지막 인덱스를 찾고,
  계산해서 리턴하면 된다고 한다.

소스코드

: lower_bound 와 upper_bound 를 사용했다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int Count(vector<int>&v, int target)
{
	auto iter_lower = lower_bound(v.begin(), v.end(), target);
	auto iter_upper = upper_bound(v.begin(), v.end(), target);

	return iter_upper - iter_lower;
}


int main() {

	int n, m;
	cin >> n >> m;

	vector<int>v;

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;
		v.push_back(input);
	}

	int cnt = Count(v, m);

	if (cnt != 0)
	{
		cout << cnt << endl;
	}
	else
		cout << "-1" << endl;

}

소스코드 - 내가 만든

#include <iostream>
#include <vector>
using namespace std;

bool BinarySearch(vector<int>&v, int target, int &inSmall, int &inBig)
{
	int start = 0;
	int end = v.size() - 1;
	

	while (start <= end)
	{
		int mid = (start + end) / 2;
		if (v[mid] == target)
		{
			//제일 작은 친구와 제일 큰 친구를 찾아야 한다. 
			while (1)
			{
				//작은친구부터 찾자.
				int small = mid;

				while (v[small] == target && small != 0)
				{
					if (v[small - 1] == target)
						small -= 1;
					else
						break;
				}
				inSmall = small;

				int big = mid;
				while (v[big] == target && big < v.size() - 1)
				{
					if (v[big + 1] == target)
						big += 1;
					else
						break;
				}
				inBig = big;

				return true;
			}
			break;
		}
		else if (v[mid] < target)
		{
			start = mid + 1;
		}
		else if (v[mid] > target)
		{
			end = mid - 1;
		}

	}

	return false;
}


int main() {

	int n, m;
	vector<int>v;

	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;
		v.push_back(input);
	}

	int small = -1, big = -1;
	if (BinarySearch(v, m, small, big))
	{
		cout << big - small + 1;
	}
	else
	{
		cout << "-1" << endl;
	}
	


}

1) 포함이 안되어 있을때의 처리를 추가해야 하고,
2) 해당 자리에서 멈춰야 한다. 왜냐하면 1 1 2 2 2 2 3 에서 만약에
1이 타겟이라고 하면 0번째 인덱스에서 멈춰야 하는데, -1까지 내려간다면,
범위 초과 발생한다. 반대로 3이 타겟이라면 size()를 벗어나게 되므로
해당 조건에 대해서 생각을 해봐야 한다.