Python - bisect 함수

bisect: 2등분[양분]하다

이진 탐색 알고리즘을 사용하여 특정 값이 있는 index를 검색한다. 오름차순으로 정렬된 리스트에서 특정한 값의 위치(index)를 찾는다.
순차 탐색은 목록을 단순 순서대로 찾아 나간다. 최대 n번까지 하게된다.

>>> import bisect
>>> l2 = [1, 2, 3, 7, 9, 11, 22, 33]
>>> bisect.bisect(l2, 7)
4
>>> l2.reverse()
>>> bisect.bisect(l2, 7)
8
>>> l2
[33, 22, 11, 9, 7, 3, 2, 1]
>>> bisect.bisect(l2, 1)
0
>>> bisect.bisect(l2, 2)
0
>>> bisect.bisect(l2, 11)
8
>>> bisect.bisect(l2, 9)
8
>>>

 

자료구조의 insert에 사용.

정렬된 상태를 유지하며 삽입되어야 할 index위치를 찾는데 사용한다.

만약 동일 값이 있을 경우 오른쪽이나 왼쪽을 구분해서 사용하는 함수 bisect_left, bisect_right, bisect은 기본 right다.

>>> l2 = [1, 2, 3, 7, 9, 11, 22, 33]
>>> bisect.bisect_left(l2, 10)
5
>>> bisect.bisect_left(l2, 11)
5
>>> bisect.bisect_right(l2, 11)
6
>>> l2.insert(bisect.bisect_left(l2, 11), 11)
>>> l2
[1, 2, 3, 7, 9, 11, 11, 22, 33]
>>>

 

 

위치를 찾아 insert까지 수행하는 함수. insort_left, insort_right, insort은 기본 right다. 

>>> l2 = [1, 2, 3, 7, 9, 11, 11, 22, 33]
>>> bisect.insort_left(l2, 11)
>>> l2
[1, 2, 3, 7, 9, 11, 11, 11, 22, 33]