-
Bisect ModuleProgramming/python 2021. 3. 9. 11:05728x90
Bisect
python에서 제공하는 패키지
이진 탐색을 쉽게 할 수 있도록 하는 함수
배열에서 특정 값을 찾는 방법은
1) for문을 앞에서부터 돌린다.
2) left, right를 둬서 이분 탐색을 한다.
bisect는 2)번을 좀 더 쉽게 할 수 있도록 만들어 놓은 함수이다.
예를 들어서 점수에 따른 등급을 찾는다고 해보자
arr = [60, 70, 80, 90] val = ['F', 'D', 'C', 'B', 'A'] print(bisect.bisect_left(arr, 89),bisect.bisect_right(arr, 89), val[bisect.bisect_right(arr, 89)]) # 3 3 B print(bisect.bisect_left(arr, 79), bisect.bisect_right(arr, 79), val[bisect.bisect_right(arr, 79)]) # 2 2 C
주의할 점
bisect_left는 값을 포함해서 계산하고, bisect_right는 그 다음 위치를 넘겨준다
무슨말이고 하니
def countRange(nums, left, right): r = bisect.bisect_right(nums, right) l = bisect.bisect_left(nums, left) print(l, r) # 2, 6 return r - l nums = [1,2,3,4,5,6,7,8,9,10] # 3~6까지 갯수 구하기 print(countRange(nums, 3, 6))
위의 예제를 보면 bisect_right는 6이 나오고, bisect_left는 2가 나온다.
nums에서 3을 찾으면 index가 2이고, bisect_left는 2를 포함해서 결과값이 나온다
반면, nums에서 6을 찾으면, index가 5이지만 bisect_right는 한칸 뒤인 6을 넘겨준다.
'Programming > python' 카테고리의 다른 글
Python Class - 4 (0) 2021.06.29 Python Class - 3 (0) 2021.06.24 Python Class - 2 (0) 2021.06.24 Python Class - 1 (0) 2021.06.24 다익스트라(Dijkstra) 알고리즘 (0) 2021.03.10