[Python] 이진 탐색 알고리즘(3) - 정렬된 배열에서 특정 수의 개수 구하기

• N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 {1,1,2,2,2,2,3}이 있을 때 x = 2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다.
• 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다.

<문제> 정렬된 배열에서 특정 수의 개수 구하기: 문제 해결 아이디어

내코드

from bisect import bisect_left, bisect_right

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

def sorted(arr, target):
    left = bisect_left(arr,target)
    right = bisect_right(arr,target)

    result=right-left
    if result >0:
        return result
    else:
        return -1

print(sorted(arr, x))

<문제> 정렬된 배열에서 특성 수의 개수 구하기: 답안 예시 (Python)

from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(array, left_value, right_value):
    left_index = bisect_left(array, left_value)
    right_index = bisect_right(array, right_value)
    return right_index - left_index

n, x = map(int, input().split()) # 데이터의 개수 N, 찾고자 하는 값 x 입력받기
array = list(map(int, input().split())) # 전체 데이터 입력받기

# 값이 [x, x] 범위에 있는 데이터의 개수 계산
count = count_by_range(array, x, x)

# 값이 x인 원소가 존재하지 않는다면
if count == 0:
    print(-1)
# 값이 x 인 원소가 존재한다면
else:
    print(count)