bisect

bisect 

- 파이썬에서 이진 탐색을 쉽게 구현할 수 있도록 해주는 라이브러리

- 정렬된 리스트에서 특정 범위에 속하는 원소 개수를 구할 때 유용함 (bisect는 숫자 데이터에서만 적용 가능!!)

- 시간복잡도 = O(logN)

import bisect

- bisect_left(리스트, 숫자 데이터) = 해당 리스트에서 지정한 숫자 데이터가 들어갈 수 있는 인덱스의 최솟값 반환

=> 오름차순으로 정렬된 리스트에서 해당 숫자 데이터보다 작은 데이터의 개수

- bisect_right(리스트, 숫자 데이터) = 해당 리스트에서 지정한 숫자 데이터가 들어갈 수 있는 인덱스의 최댓값 반환

=> 오름차순으로 정렬된 리스트에서 해당 숫자 데이터보다 큰 숫자 데이터의 개수

 

ex) A=리스트, a, b= 서로 다른 숫자 

- bisect_right(A, a) - bisect_left(A, a) = A에서 a의 개수 (> 0이면 해당 리스트 A에 a가 존재함을 알 수 있음) 

- bisect_right(A, b) - bisect_left(A, a) = A에서 [a,b]의 범위에 속하는 원소의 개수 

=> 시간복잡도가 n인 count보다 처리속도가 빠름

 

활용문제

https://github.com/anydevil0812/coding_test/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv2/42747.%E2%80%85H%EF%BC%8DIndex

GitHub - anydevil0812/coding_test: 코딩 테스트