정렬된 배열에서 특정 수의 개수 구하기

💻 입력 조건

• 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다.
  ($1 <= N <= 1,000,000$), ($-10^9 <= x <= 10^9$)
• 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다.
  ($-10^9 <=$ 각 원소의 값 $<= 10^9$)

💻 출력 조건

• 수열의 원소 중에서 값이 x인 원소의 개수를 출력합니다. 단, 값이 x인 원소가 하나도 없다면 -1을 출력합니다.

💻 입력 예시 1

7 2
1 1 2 2 2 2 3

💻 출력 예시 1

4

💻 입력 예시 2

7 4
1 1 2 2 2 2 3

💻 출력 예시 2

-1

📖 문제 해결
문제에서 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과'판정을 받는다고 명시해 놓았고, 오름차순으로 정렬되어 있기에 이진 탐색을 활용하여 문제를 해결하였습니다. 구하고자 하는 것이 오름차순으로 정렬되어 있는 수열 내에서 x가 등장하는 횟수이기 때문에 x가 처음으로 등장한 시점의 인덱스(start_index), 그리고 x가 나오는 것이 마지막인 시점의 인덱스(end_index)를 구하고 이 둘의 차에 1을 더함으로써 x가 등장하는 횟수를 구하였습니다.

# n, x 입력받기
n, x = list(map(int, input().split()))

# input_list 입력받기
input_list = list(map(int, input().split()))

# x의 등장이 시작하는 위치의 인덱스를 반환하는 함수
def start_search(array, target, start, end):
    
    while start <= end :
        
        mid = (start + end) // 2
        
        if (mid == 0 or array[mid-1] != target) and array[mid] == target:
            return mid
        
        elif array[mid] < target :
            start = mid + 1
        
        elif array[mid] >= target :
            end = mid - 1
    
    return None

# x의 등장이 끝나는 위치의 인덱스를 반환하는 함수
def end_search(array, target, start, end):
    
    while start <= end :
        mid = (start + end) // 2
        
        if (mid == n-1 or array[mid+1] != target) and array[mid] == target:
            return mid
        
        elif array[mid] <= target :
            start = mid + 1
        
        elif array[mid] > target :
            end = mid - 1
    
    return None

# start_index 찾기
start_index = start_search(input_list, x, 0, n-1)

# end_index 찾기
end_index = end_search(input_list, x, 0, n-1)

# 만약 x인 원소가 하나도 없다면 -1을 출력
if start_index == None:
    print(-1)
    
# 그렇지 않다면 start_index와 end_index를 이용하여
# x가 등장하는 횟수를 계산
else:
    print(end_index - start_index + 1)