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

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 30

1. 문제 설명

- 정렬된 배열에서 특정 수의 개수 구하는 문제

2. 접근 방식

- 처음에는 이진탐색을 이용해 값을 찾고, 후에는 그 주위로 퍼져 나가는 느낌으로 값을 찾으려고 했다. 해당 문제의 경우 백준 등에 게시된 문제가 아니라서 정답을 확인할 수 없었다.

- 하지만 bisect 라이브러리를 활용해 쉽게 풀 수 있었다.

3. 코드

- 초기 코드

def binary_search(start, end, target):
    if start > end:
        return -1
    mid = (start+end) // 2
    if ls[mid] == target:
        return mid #인덱스 리턴
    if ls[mid] < target:
        return binary_search(start, mid-1, target)
    elif ls[mid] > target:
        return binary_search(mid+1, end, target)
    
idx = binary_search(0, n, x)

if idx == -1:
    print(-1)
else:
    right_idx = idx+1
    left_idx = idx-1
    while ls[right_idx] == x:
        right_idx += 1
    while ls[left_idx] == x:
        left_idx -= 1
    print(right_idx, left_idx)
    print(right_idx-left_idx-1)

- 해답 코드

from bisect import bisect_left, bisect_right

def count_by_range(array, left_value, right_value):
    right_index = bisect_right(array, right_value)
    left_index = bisect_left(array, left_value)
    return right_index - left_index

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

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

4. 코멘트

- from bisect import bisect_left, bisect_right....메모메모