파이썬(Python) - 이분탐색(이진탐색) / bisect

이진 탐색(이분 탐색)

• 정렬된 상태의 리스트에서 탐색범위를 반으로 줄여가며 데이터를 탐색하는 방법
• 리스트가 반드시 정렬된 상태여야만 한다.

< 예시 >

lst = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]  # 오름차순으로 정렬된 상태
num = 7  # 정렬된 상태를 유지하며 배열에 추가할 요소

left = 0 # 왼쪽 기준 인덱스
right = len(lst)-1 # 오른쪽 기준 인덱스

while left<=right:
	mid = (left + right)//2
	if lst[mid]>= num:
    	right = mid - 1
        result = mid
    else:
    	left = mid + 1
        
print(result)  # 7

• 각 양끝의 인덱스를 기준으로 잡고 가운데 인덱스를 비교값을 삼아 범위를 반씩 줄여나가는 방식
• 절반씩 범위를 줄여가기에 O(logN)이 성립!

 

bisect - bisect_left / bisect_right

• 위의 이분탐색을 편하게 할 수 있게 해주는 모듈
• bisect_left(배열, 넣을 요소) : 정렬된 상태를 유지하며 넣을 요소를 삽입할 가장 앞쪽(왼쪽) 인덱스를 반환
• bisect_right(배열, 넣을 요소) : 정렬된 상태를 유지하며 넣을 요소를 삽입할 가장 뒤쪽(오른쪽) 인덱스를 반환

<예시1>

from bisect import bisect_left, bisect_right

lst = [0, 1, 2, 5, 5, 5, 5, 6, 7, 8]
num = 5

print(bisect_left(lst, num)) # 3
print(bisect_right(lst, num)) # 6

<예시2 - 정렬된 리스트에서 특정범위 원소의 개수 구하기>

import time
import bisect
import numpy as np
# 1~100까지의 수를 랜덤으로 크기가 10000인 리스트 생성
lst = sorted(np.random.randint(1, 101, size = 10000))
#특정 범위의 수를 세는 메서드
def count_range(lst, left_value, right_value):
    left_index = bisect.bisect_left(lst, left_value)
    right_index = bisect.bisect_right(lst, right_value)
    return f"{left_value} ~ {right_value} 범위의 수 : {right_index-left_index}개"
start1 = time.time() # 시작시간
print(count_range(lst, 10, 50)) # 4174
end1 = time.time() #종료시간
print(f"bisect 실행시간 : {end1 - start1}초") # 0.0006866초


start2 = time.time()
cnt = 0
# 리스트 전체를 체크
for i in lst:
    if i>=10 and i<=50:
        cnt+=1
print(f"5 ~ 7 범위의 수 : {cnt}개") # 4174
end2 = time.time()
print(f"count 실행시간 : {end2 - start2}초") # 0.0050103초 : bisect활용한 방법의 약 7배