bisect는 이진탐색을 도와주는 함수다!
데크나 힙처럼 다해주는건 아닌데 대충 도와준다!
이진탐색을 도와준다는게 어려워보이지만 그냥 정렬되어 있는 리스트에서 정렬을 흩트리지 않아도 되는 부분의 '인덱스'를 엄청 빠른 속도로 찾아주는 모듈이다.
.bisect(literable, value) : 이터러블한 객체, 찾는 값을 입력하면 그 값의 인덱스를 반환한다. 그 값의 인덱스가 없을때는 여기에 insert하면 정렬이 안깨질 것 같은 값을 오른쪽에다가 반환한다. 어쨌든 값 자체가 반환되는게 아니라는 것에 주의!
(bisect와 bisect_right는 같은 일을 한다.)
import bisect
result = []
scores = [33, 99, 77, 70, 89, 90, 100] # 애들이 받은 점수
grades = [60, 70, 80, 90] # 기준점수를 등급으로 바꿔주자
for score in scores:
pos = bisect.bisect(grades, score)
# 학생들의 점수를 grades = 기준에 넣는다고 가정했을때 어디 들어가면 될까
grade = 'FDCBA'[pos] # bisect는 인덱스만 리턴한다.
result.append(grade)
print(result)
['F', 'A', 'C', 'C', 'B', 'A', 'A'].bisect_left(literable, value) : 이터러블한 객체, 찾는 값을 입력하면 얘는 왼쪽에서부터 세어서 그 값의 인덱스를 반환한다. 이상 초과 미만을 구현하기 좋다. 그 값의 인덱스가 없을때는 여기에 insert하면 정렬이 안깨질 것 같은 값을 인덱스의 왼쪽에 반환한다. 왼쪽 오른쪽으로 나뉘는 걸 제외하면 같은 기능이다.
bisect의 push함수!
bisect.insort(literable, value) : insert와 비슷한 역할, 정렬이 될 수 있는 위치를 자동으로 찾아서 들어간다!
insort_right도 있다!
>>> import bisect
>>> a = [60, 70, 80, 90]
>>> bisect.insort(a, 85)
>>> a
[60, 70, 80, 85, 90]bisect로 특정 수의 갯수 구하기!
- 이건 자체기능은 아니고 응용!
- 정렬하기
- bisect(list, target)
- bisect_left(list, target)
- bisect - bisect-left = target이 몇개 있는지 나온다!
- 이제 이걸 함수로 만들어서 list, value를 인자로 넣어주면 정렬된 ri는 오른쪽에서 제일 처음 찾은 값, li는 왼쪽에서 제일 처음 찾은 값이니까 오름차순일때 오른쪽에서 왼쪽을 빼주면 그 수의 범위가 된다.
import bisect
def count_bi(nums, value):
ri = bisect(nums, value)
li = bisect_left(nums, value)
return ri - li
nums = [-1, -3, 5, 5, 4, 7, 1, 7, 2, 5, 6]
nums.sort() # 정렬은 필수
print(count_bi(nums, 5))
3- 응용의 응용! 인자를 nums, left_value, right_value 셋 다 지정해주면 n부터 k까지의 범위도 구할 수 있다. 정렬된 배열에서 특정 수의 갯수 구하기에 아주 좋다.
import bisect
def count_bi(nums, left_value, right_value):
ri = bisect(nums, right_value)
li = bisect_left(nums, left_value)
return ri - li
nums = [-1, -3, 5, 5, 4, 7, 1, 7, 2, 5, 6]
nums.sort() # 정렬은 필수
print(count_bi(nums, 5, 7)) # 5 ~ 7이 몇개나 있는지 구하기
6효율성 높이기!
bisect, bisect_left, insort 이거 세개만 알면 되고 추가로 효율성을 위해서 알면 좋은 거! 함수 안에 ,구분자로 들어가는 lo와 hi이다.
bisect.bisect_left(a, x, lo=0, hi=len(a)) # 리스트, 값, 왼쪽, 오른쪽lo, hi는 left와 right를 의미한다.
if문 사용시 다음에 주의해야 한다고 써있는데
bisect_left()
a[mid] < target => lo = mid + 1
a[mid] >= target => hi = midbisect_right()
a[mid] <= target => lo = mid + 1
a[mid] > target => hi = mid범위를 어느정도 알고 있을때 줄어드는 부분 이해하기!
bisect_left()는 중복이 있는 경우, hi를 줄여 최대한 왼쪽으로,
bisect_right()는 lo을 늘려 최대한 서치범위를 줄이면 좋다!
