Python - 이진검색 bisect

이진 검색은 정렬된 배열에서 원하는 원소를 빠르게 찾을 수 있다. --> O(logn)
현재 값이 찾으려는 값보다 작으면 오른쪽으로 이동, 크면 왼쪽으로 이동하는 것을 이용한다.
Python에서는 이런 기능을 가진 함수를 제공한다.

bisect_left(a,x) , bisect_right(a,x)

from bisect import bisect_left,bisect_right

는 정렬된 a에 x를 삽입할 위치를 알려준다. a에 x가 이미 존재하면 x의 left는 앞, rigth는 뒤 위치를 반환한다.

list=[1,3,4,5,6,6,8]이라고할때

bisect_left(list1,1) = 0
bisect_right(list1,1) = 1

bisect_left(list1,6) = 4
bisect_right(list1,6) = 6

bisect_left(list1,8) = 6
bisect_right(list1,8) = 7

뭔가 조금 햇갈린다. list=[1,3,4,5,6,6,8]의 위치를 [1,2,3,4,5,6,7]이라고 했을때
x가 존재할때 left는 처음 나오는 x의 위치, right는 마지막 x의 위치+1 이다.

이 위치로 해당 숫자보다 작은 수의 개수, 큰 수의 개수를 쉽게 구할 수 있다.

bisect_left(list1,6) = 4의 경우 6보다 작은 숫자는 4개
bisect_right(list1,6) = 6의 경우 전체길이 7-6 하면 6보다 큰 숫자는 1개

그리고 lo, hi를 이용해 검색영역을 지정할 수 있다.

bisect_left(list1,6,lo=0,hi=6) = 6
bisect_right(list1,6,lo=0,hi=6) = 6

bisect_left(list1,6,lo=1,hi=6) = 6
bisect_right(list1,6,lo=1,hi=6) = 6
lo가 0이나 1이나 같다. 아래의 경우에도 마찬가지였다.

bisect_left(list1,6,lo=0,hi=7) = 6
bisect_right(list1,6,lo=0,hi=7) = 7

bisect_left(list1,6,lo=0,hi=8) = 6
bisect_right(list1,6,lo=0,hi=8) = 8

bisect_left(list1,6,lo=0,hi=10) = 6
bisect_right(list1,6,lo=0,hi=10) = 8

검색 영역이 다를때, 결과값도 달라짐을 알 수 있다.

또한 insort() 함수를 이용해 해당 위치에 값을 넣을 수 있다.

insort()

import bisect

bisect.insort_left(a, x)
오름차순 a에 x값을 동일한값 위치에 삽입한다.
bisect.insort_right(a, x)
오름차순 a에 x값을 동일한값 바로뒤에 삽입한다.

bisect.insort_left(list1, 4)
[1, 2, 2, 3, 4, 4, 5, 6, 6] // 4 왼쪽에 4추가
bisect.insort_right(list1, 5) // 5 오른쪽에 5추가
[1, 2, 2, 3, 4, 4, 5, 5, 6, 6]