[zoho 인터뷰/이진탐색] 정렬된 배열에서 특정 수의 개수 구하기

오름차순으로 정렬된 리스트에서 주어진 숫자가 몇개 있는지 출력하는 코드를 작성해야하는 문제였다.

시간 복잡도가 O(logN)이어야 한다. 

그래서 완전 탐색보다는 이진탐색으로 풀어야 하는 문제다. 

일반적인 이진탐색보다는 주어진 숫자가 시작하는 인덱스와 끝나는 인덱스를 구한 후 그 두 인덱스의 차이를 구하면 되는데

다른 방법으로는 내부 함수를 이용하면된다. bisect_left와 bisect_right다

 

-정답풀이:

from bisect import bisect_left,bisect_right

def count_by_range(data,left_value,right_value):
	right_index=bisect_right(data,right_value)
    left_index = bisect_left(data,left_value)
    return right_index-left_index
    
n,x=map(int,input().split())
data=list(map(int,input().split()))

count=count_by_range(data,x,x)
if count==0:
	print(-1)
else:
	print(count)