이진탐색 - bisect

< 정의 >

정렬된 데이터를 이진 탐색 할때 사용하는 파이썬의 라이브러리 

 

 

< 형태 > 

from bisect import bisect_left, bisect_right 

left_index = bisect_left(array, value, low(범위), high(범위)) # (low(범위) ~ high(범위))내에 있는 값 
left_index = bisect_left(array, value) 

right_index = bisect_right(array, value, low(범위), high(범위)) # (low(범위) ~ high(범위))내에 있는 값 
right_index = bisect_right(array, value)

 

 

bisect_left(left_index = bisect_left(array, value, low범위), high범위))

= bisect_left(array, value) 

: 정렬된 array에서 (low ~ high)까지 범위내  value이 들어갈 만한 곳의 '왼쪽'에 넣어 index를 return

 

 

 

bisect_right(array, value, low(범위), high(범위)) 
= bisect_right(array, value)

: 정렬된 array에서 (low ~ high)까지 범위내 value이 들어갈 만한 곳의 '오른쪽'에 넣어 index를 return

 

 

 

 

< 범위내 데이터 개수 구하기 >

from bisect import bisect_left, bisect_right 

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