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) = 1bisect_left(list1,6) = 4
bisect_right(list1,6) = 6bisect_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) = 6bisect_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) = 7bisect_left(list1,6,lo=0,hi=8) = 6
bisect_right(list1,6,lo=0,hi=8) = 8bisect_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]
Author And Source
이 문제에 관하여(Python - 이진검색 bisect), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@areum0921/Python-이진검색-bisect저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)