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

 

 

 

유형 분석 및 구현

이 문제는 직접 이진탐색을 구현한다기 보단, 파이썬에서 제공하는 이진탐색을 활용한 탐색 방법을 사용한다.

순차적 탐색과 비교해보면

최대 100만개에 데이터 중에서 최대 100만개의 데이터를 찾아야한다.

하지만 이진 탐색을 활용하면 확 줄어든다.

 

 

 

코드

from bisect import bisect_left, bisect_right

n = 7
x = 2
array = [1, 1, 2, 2, 2, 2, 3]

left_index = bisect_left(array, x)
right_index = bisect_right(array, x)
print(left_index, right_index)
result = right_index-left_index

if result == 0:
    print("-1")
else:
    print(result)