[python] 이진탐색 라이브러리 bisect

이진탐색 알고리즘을 푸는 경우 유용한 bisect 라이브러리를 활용해본다.

• bisect_left(a,x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환
• bisect_right(a,x) : 정렬된 순서를 유지하면서 배열a에 x를 삽입할 가장 오른쪽 인덱스 반환

bisect를 이용하여 값이 특정 범위에 속하는 데이터 개수 구하기

from bisect import bisect_left, bisect_right
def count_by_range(a,left_value, right_value):
    right_index = bisect_right(a,right_value)
    left_index = bisect_left(a,left_value)
    return right_index - left_index

a = [1,2,3,3,3,4,4,8,9]
print(count_by_range(a,4,4))  ## 값이 4인 데이터 개수 출력
print(count_by_range(a,-1,3)) ## 값이 [-1,3]범위에 있는 데이터 개수 출력

 

(응용)정렬된 배열에서 특정 수의 개수 구하기

• N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬된 경우 x가 등장하는 횟수를 계산하라
• x인 값이 하나도 없다면 -1 출력
• logN 시간복잡도로 작성

from bisect import bisect_left, bisect_right
n,x = list(map(int,input().split()))
array = list(map(int,input().split()))

def solution(array,x):
    if x not in array:
        return -1
    else:
        return bisect_right(array,x) - bisect_left(array,x)
print(solution(array,x))