파이썬(python) 라이브러리 - bisect (이진탐색, 바이너리 서치, Binary Search)

---

이진탐색 (바이너리 서치, Binary Search)

---

정렬된 리스트에서 탐색 범위를 절반씩 좁혀나가며 빠르게 탐색하는 방법 

 

특징

탐색 범위가 매우 크게 주어짐 O(n) 인 선형탐색으로는 시간초과 나는 경우 사용가능

정렬된 리스트에서 특정 값을 매우 빠르게 찾고 싶을때 사용 

시간 복잡도 O(log N)

 

구현

1. bisect 라이브러리 사용

bisect.bisect_left(정렬된 리스트, target)

정렬된 리스트에서 target을 insert할때의 위치

 

bisect.bisect_right(정렬된 리스트, target)

정렬된 리스트에서 target을 insert할때의 위치+1

※ bisect.bisect는 bisect.bisect_right와 동일함

 

bisect.insert() 함수는 bisect함수와 동일하게 작동하고 해당 인덱스에 값을 삽입을 해준다.

(이 함수들은 c++의 upper_bound, lower_bound와 동일 → 대신 )

import bisect
a = [1,2,3,4,5]
x = 3
b = bisect.bisect_left(a,x)
2와 3 사이 인덱스인 2반환

c = bisect.bisect_right(a,x)
3과 4 사이 인덱스인 3반환

정렬된 리스트에서 특정 값이 몇번 등장하는지 확인
bisect.bisect_right(a, right) - bisect.bisect_left(a, left)

 

2. 직접 구현

def binary_serach(arr, target, start, end):
    while start <= end:
        mid = (start+end)//2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            end = mid-1
        else:
            start = mid + 1
    return None

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
(start ,mid, end)
(0, 5, 10)

if mid > target: 
(start ,mid, end)
(0, 2, 4)

elif mid > target:
(start ,mid, end)
(6, 8, 10)

 

 

예시

백준 12015 : 가장 긴 증가하는 부분 수열 2

12015번: 가장 긴 증가하는 부분 수열 2

import sys, bisect
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
inc_arr = [int(1e9)]*n

for i in range(0,n):
    idx = bisect.bisect_left(inc_arr, arr[i])
    if idx < n:
        inc_arr[idx] = arr[i]
        print(idx, arr[i],inc_arr)

print(inc_arr)

8
10 20 30 5 10 20 30 40

(idx, arr[i], inc_arr)
0 10 [10, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000]
1 20 [10, 20, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000]
2 30 [10, 20, 30, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000]
0 5 [5, 20, 30, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000]
1 10 [5, 10, 30, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000]
2 20 [5, 10, 20, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000]
3 30 [5, 10, 20, 30, 1000000000, 1000000000, 1000000000, 1000000000]
4 40 [5, 10, 20, 30, 40, 1000000000, 1000000000, 1000000000]

정답
5

---

파라메트릭 서치 (Parametric Serch)

---

최적화 문제를 결정 문제(Yes or No)로 바꾸어 해결하는 기법

특정 조건 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제에 사용됨

 

특징

탐색 범위가 매우 크게 주어짐 O(n) 인 선형탐색으로는 시간초과 나는 경우 사용가능

정렬된 리스트에서 범위를 중간값으로 잘랐을때 특정 조건을 만족하는지 확인할 때 사용됨

 

구현

바이너리 서치 함수 안에서 중간값으로 잘랐을때 어떤 조건을 만족하는지 확인

 

예시

백준 2805 : 나무 자르기

2805번: 나무 자르기

import sys
n,m = map(int,sys.stdin.readline().split())
target = list(map(int,sys.stdin.readline().split()))
s = 0
e = 2**31-1
while s <= e:
    mid = (s+e)//2
    cnt = 0
    for t in target:
        if t > mid:
            cnt += t-mid
    if m <= cnt:
        s = mid+1
    else:
        e = mid-1
print(e)