[이코테] 이진 탐색 문제 - 정렬된 배열에서 특정 수의 개수 구하기

문제

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요.
단, 이 문제의 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다.

입력 예시

7 2
1 1 2 2 2 2 3

출력 예시

4

---

n, x = map(int, input().split())
graph = list(map(int, input().split()))

countA = -1
countB = -1
start = 0
end = len(graph) - 1

# 처음 등장하는 인덱스와 마지막으로 등장하는 인덱스

while(start <= end):
    mid = (start + end) // 2
    # print(mid)
    if ((mid == 0 or x > graph[mid - 1]) and graph[mid] == x): # 찾은 경우
        countA = mid
        break
    elif (graph[mid] >= x):
        end = mid - 1
    else:
        #  (graph[mid] <= x):
        start = mid + 1

# print(countArr)
start = 0
end = len(graph) - 1
while(start <= end):
    mid = (start + end) // 2
    # print(mid)
    if ((mid == len(graph) - 1 or x < graph[mid + 1]) and graph[mid] == x): # 찾은 경우
        countB = mid
        break
    elif (graph[mid] <= x):
        start = mid + 1
    else:
        #  (graph[mid] <= x):
        end = mid - 1

# print(countArr)
result = countB - countA + 1

if (countA == -1):
    print(-1)
elif (result == 0):
    print(-1)
else:
    print(result)