binary search
- 🛑정렬된 배열에서 원소를 빠르게 찾을 수 있는 방법이다
- 시간 복잡도 :
Q(logN)
✋bisect(a, x)
- 정렬된 a에 대하여,
x가 정렬순서에 맞게 들어갈 위치 = 삽입된 후 위치를 반환한다- bisect = bisect_right
✋bisect_left(a, x)
- 정렬된 a에 대하여,
✅x가 a에 이미 있으면 👉기존 항목의 x의 위치를 반환
✅x가 a에 여러개 있으면 👉가장 첫번째 x의 위치를 반환
✅x가 a에 없으면 👉정렬 순서에 맞게 x가 들어갈 위치를 반환
def bisect_left(a, x, lo=0, hi=None):
"""Return the index where to insert item x in list a, assuming a is sorted.
The return value i is such that all e in a[:i] have e < x, and all e in
a[i:] have e >= x. So if x already appears in the list, a.insert(x) will
insert just before the leftmost x already there.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
# Use __lt__ to match the logic in list.sort() and in heapq
if a[mid] < x: lo = mid+1
else: hi = mid
return lo
✋bisect_right(a, x)
- 정렬된 a에 대하여,
✅x가 a에 이미 있으면 👉기존 항목 x의 위치 + 1을 반환
✅x가 a에 여러개 있으면 👉가장 마지막 x의 위치 + 1을 반환
✅x가 a에 없으면 👉정렬 순서에 맞게 x가 들어갈 위치를 반환
def bisect_right(a, x, lo=0, hi=None):
"""Return the index where to insert item x in list a, assuming a is sorted.
The return value i is such that all e in a[:i] have e <= x, and all e in
a[i:] have e > x. So if x already appears in the list, a.insert(x) will
insert just after the rightmost x already there.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
# Use __lt__ to match the logic in list.sort() and in heapq
if x < a[mid]: hi = mid
else: lo = mid+1
return lo✍예제1
from bisect import bisect_left, bisect_right, bisect
# 2가 nums에 이미 있으면
nums = [0, 1, 2, 3, 4, 5]
print(bisect_left(nums, 2)) # 2 👉 2의 원래 위치 반환
print(bisect_right(nums, 2)) # 3 👉 2의 원래 위치 +1 반환
print(bisect(nums, 2)) # 3 👉 2가 들어갈 위치 반환 = 삽입된 뒤 위치 반환
# 2가 nums에 없으면
nums = [0, 1, 3, 3, 4, 5]
print(bisect_left(nums, 2)) # 2 👉 2가 들어갈 위치 반환
print(bisect_right(nums, 2)) # 2 👉 2가 들어갈 위치 반환
print(bisect(nums, 2)) # 2 👉 2가 들어갈 위치 반환
# 2가 nums에 여러개 있으면
nums = [0, 1, 2, 2, 4, 5]
print(bisect_left(nums, 2)) # 2 👉 가장 첫번째 2의 원래 위치 반환
print(bisect_right(nums, 2)) # 4 👉 가장 마지막 2의 원래 위치 +1 반환
print(bisect(nums, 2)) # 4 👉 2가 들어갈 위치 반환✍예제2
from bisect import bisect_left, bisect_right, bisect
nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(bisect_left(nums, 5)) # 5 👉 5의 원래 위치 반환
print(bisect_right(nums, 5)) # 6 👉 5의 원래 위치+1 반환
nums = [4, 5, 5, 5, 5, 5, 5, 5, 5, 6]
print(bisect_left(nums, 5)) # 1 👉 가장 첫번째 2의 원래 위치 반환
print(bisect_right(nums, 5)) # 9 👉 가장 마지막 2의 원래 위치+1 반환
nums = [1, 3, 3, 3, 5]
print(bisect_left(nums, 0)) # 0 👉 0이 들어갈 위치 반환
print(bisect_right(nums, 0)) # 0 👉 0이 들어갈 위치 반환
print(bisect_left(nums, 1)) # 0 👉 1의 원래 위치 반환
print(bisect_right(nums, 1)) # 1 👉 1의 원래 위치+1 반환
print(bisect_left(nums, 2)) # 1 👉 2가 들어갈 위치 반환
print(bisect_right(nums, 2)) # 1 👉 2가 들어갈 위치 반환
print(bisect_left(nums, 3)) # 1 👉 가장 첫번째 3의 원래 위치 반환
print(bisect_right(nums, 3)) # 4 👉 가장 마지막 3의 원래 위치+1 반환
print(bisect_left(nums, 4)) # 4 👉 4가 들어갈 위치 반환
print(bisect_right(nums, 4)) # 4 👉 4가 들어갈 위치 반환
print(bisect_left(nums, 5)) # 4 👉 5의 원래 위치 반환
print(bisect_right(nums, 5)) # 5 👉 5의 원래 위치+1 반환
print(bisect_left(nums, 6)) # 5 👉 6이 들어갈 위치 반환
print(bisect_right(nums, 6)) # 5 👉 6이 들어갈 위치 반환
nums = [1, 3, 4, 5]
print(bisect(nums,2)) # 1 👉 1이 들어갈 위치 반환✋insort_left(a, x)
- x와 동일한 값이 시퀀스 a에 존재할 때 x와 동일한 값 위치에 x를 삽입한다
- insort = insort_right
✋insort_right(a, x)
x와 동일한 값이 시퀀스 a에 존재할 때 x와 동일한 값 바로 뒤 위치에 x를 삽입한다.
✍예제
import bisect
nums = [1, 3, 4, 5]
bisect.insort(nums, 2)
print(nums) # [1, 2, 3, 4, 5]
nums = [1, 3, 4, 5]
bisect.insort_left(nums, 2)
print(nums) # [1, 2, 3, 4, 5]
nums = [1, 3, 4, 5]
bisect.insort_right(nums, 2)
print(nums) # [1, 2, 3, 4, 5]