[파이썬 코딩의 기술] - 72. 정렬된 시퀀스를 검색할 때는 bisect를 사용하라

Q. 리스트에 들어있는 정렬된 데이터를 검색하고 싶을 땐?

bisect

• 파이썬에서 제공하는 표준 라이브러리.
• 이진 검색 알고리즘을 이용해서 시퀀스를 검색하고, 시퀀스에 항목을 삽입할 수 있는 함수 제공
• 이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘
• bisect() : 오름차순으로 정렬된 시퀀스에 x값이 들어갈 위치 리턴.
• 기본적으로 시퀀스 전체를 범위로 함.
• bisect_right() : x와 동일한 값이 시퀀스 a에 존재할 때 x와 동일한 값 바로 뒤 위치를 리턴
• bisect_left() : x와 동일한 값이 시퀀스 a에 존재할 때 동일한 값 위치를 리턴. 리스트에 찾는 값의 원소가 존재하지 않는 경우 정렬 순서상 해당 값을 삽입해야 할 자리의 인덱스.

import bisect
sequence = [1,3,4,5]
print(bisect.bisect(sequence,2))

• 2는 [1]위치에 들어가게 됨.

import bisect
sequence = [1, 3, 4, 5]
print(bisect.bisect_right(sequence, 3))
print(bisect.bisect_left(sequence, 3))

• 3이 들어갈 위치 뒷 값은 4 위치 -> [2]

• 동일한 값이 있으므로 3의 위치 -> [1]

• 정렬된 배열 [0,1,2,3,4,5,6,7,8,9] 있을 때, 현재 정렬된 상태를 유지하면서 n=5 이라는 요소를 배열에 추가하자.

• 이분 탐색을 사용하지 않고 구현
  

• 이분탐색 사용해서 구현
  

• bisect 대량 리스트 검색 시 속도 빠름
  

요약
1. 리스트에 들어 있는 정렬된 데이터를 검색할 때 bisect 내장 모듈의 bisect_left 함수를 사용하자! 시간이 빠르다.