정렬된 배열에서 K의 등장 횟수

이진 탐색 두 번

배열이 정렬되어 있어서 가능한 풀이이다. lower_bound와 upper_bound 두 함수를 만든다.

• $\text{lower\_bound}(K)$: $A_i \ge K$인 가장 왼쪽 인덱스 $i$
• $\text{upper\_bound}(K)$: $A_i > K$인 가장 왼쪽 인덱스 $i$

그러면 $K$의 등장 횟수는 $\text{upper\_bound}(K) - \text{lower\_bound}(K)$이다.

이진 탐색을 두 번 하면 한 질의당 $O(\log N)$. 전체 $O(N + Q \log N)$.