[알고리즘] 이진탐색 Lower/Upper Bound | Python bisect

개요

이진탐색을 하는데 만약 배열에 target 값이 여러 개 존재한다면, 정확한 위치의 값을 도출하는 데에 어려움을 겪을 것이다.

이를 해결하기 위한 알고리즘이 Upper Bound와 Lower Bound이다. Python에서는 bisect라는 도구를 제공한다.

 

---

Lower Bound

target 이상의 값이 최초로 나오는 위치다. 즉, target보다 같거나 큰 원소 중 가장 작은 값의 위치다.

 

예를 들어서 아래와 같이 정렬된 배열이 존재한다고 가정하자.

1

5

5

5

10

11

100

 

이 배열의 lower_bound(5) = 5다. 또한 lower_bound(4) = 5다.

가장 작은 값을 구하기 위해서 min_idx 변수를 활용하여 초기값으로 답이 될 수 없는 최댓값을 넣어놓고 문제를 해결한다.

 

left=0
right=len(arr)-1
lower_idx=len(arr) # 최대값인 리스트의 길이로 초기화한다.

# 이진탐색 시작
while left <= right : 
	mid=(left + right)//2
    
    if arr[mid] >= target:
    	lower_idx=min(lower_idx, mid)
        right=mid-1
    else:
    	left=mid+1

if (lower_idx <= n) and (target == arr[lower_idx]):
	print('최초 idx')

 

 

arr의 원소가 target 값보다 같거나 크다면, 왼쪽에 조건을 만족하는 숫자가 있을 가능성이 크기 때문에, right를 조정한다.

이때 min_idx 변수를 통해 같거나 큰 값들의 위치 중 최솟값을 계속 갱신해준다.

 

---

Upper Bound

Upper Bound는 원하는 값을 초과하는 값이 최초로 나오는 위치를 출력하는 알고리즘이다.

즉, 원하는 값이 존재하는 인덱스 + 1번째의 값을 반환한다.

 

 

 

전체 코드

n,m=map(int,input().split())
points=sorted(map(int,input().split()))

def lower_bound(target):
    low_idx=n
    start,end=0,n-1

    while start<=end:
        mid=(start+end)//2
        if points[mid] >= target:
            low_idx=min(low_idx,mid)
            end=mid-1
        else:
            start=mid+1

    return low_idx

def upper_bound(target):
    up_idx=n
    start,end=0,n-1

    while start<=end:
        mid=(start+end)//2
        if points[mid] > target:
            up_idx=min(up_idx,mid)
            end=mid-1
        else:
            start=mid+1

    return up_idx


for _ in range(m):
    x1,x2=map(int,input().split())
    cnt=upper_bound(x2)-lower_bound(x1)
    print(cnt)

---

Lower/Upper Bound 활용

Lower Bound와 Upper Bound 특성을 통해 찾고자 하는 값의 개수와, 존재 여부를 알 수 있다.

 

• if L - U == 0 : 찾고자 하는 값 존재 X
• else : L-U찾고자 하는 값이 배열에 존재하는 개수