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

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 {1,1,2,2,2,2,3}이 있을 때 x=2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다.

단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 시간 초과 판정을 받습니다.

입력

• 첫째 줄 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다.
• 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다.

출력

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

import sys
input = sys.stdin.readline

N, x = map(int, input().split())
l = list(map(int, input().split()))


count = 0
start = 0
end = N-1
# 어떻게 해야 하지
# 1 1 2 2 2 2 3
# 0 1 2 3 4 5 6

# 2보다 작은 것 중애 가장 큰 것 idx
# 2보다 크것 중에 가장 작은 것 idx
# 아래 - 위 - 1

small_idx = 0
while start <= end:
    mid = (start + end) // 2
    if l[mid] >= x:  # 작은 것을 찾는 것이므로 크거나 같으면 왼쪽 리스트 찾기
        end = mid - 1
        continue

    if l[mid] < x:
        if l[small_idx] <= l[mid]:
            small_idx = mid
        start = mid + 1

start = 0
end = N-1
big_idx = N - 1
while start <= end:
    mid = (start + end) // 2
    if l[mid] <= x:  # 큰 것을 찾는 것이므로 작거나 같으면 오른쪽 리스트 찾기
        start = mid + 1
        continue

    if l[mid] > x:
        if l[big_idx] >= l[mid]:
            big_idx = mid
        end = mid - 1


print(big_idx - small_idx - 1)