[알고리즘] Lower Bound와 Upper Bound

아무 의미 없는 그림

✏️ 무엇인가?

Lower Bound와 Upper Bound는 모두 경계값을 찾는 과정이다. 이진탐색(Binary Search)가 '원하는 값을 찾는 과정' 이었다면 Lower Bound는 '원하는 값이 처음 나오는 위치'를 찾는 과정이고, Upper Bound는 '원하는 값이 나오는 마지막 위치를 찾는 과정'이다.

Array = [1, 1, 2, 2, 3, 4, 4, 4, 6]

이런 리스트가 있에서 Lower Bound로 4를 찾는다면 4가 처음 나오는 인덱스인 5가 Output이 될 것이고, Upper Bound로 찾는다면 4가 마지막으로 나오는 인덱스인 7이 Output이 될 것이다.

 

✏️ 구현과정의 고민

사실 선형 탐색으로 구현하면 바로 해결되지만 기왕이면 O(N)보다는 O(lgN)이 좋지 않겠나. 이진탐색으로 구현해보자. 

def BS(array, target, start, end):
  if start > end:
    return 0
  mid=(start+end)//2
  if array[mid]==target:
    return 1
  elif array[mid]>target:
    return BS(array, target, start, mid-1)
  else:
    return BS(array, target, mid+1, end)

위는 원하는 값이 존재할때 1을 출력( array[mid]==target )하는 이진탐색함수를 재귀방식으로 구현한 것이다. 해당 코드는 값이 여러개 존재할때의 경우를 전혀 고려하지 않는다. 같은 원소가 여러개 존재해도 항상 유일한 해를 구하기 위해 어떤 값을 찾으면 될까?

우선 반복문으로 이진탐색을 다시 구현하겠다.

 

(Binary Search)

def BS(array, target):
  start, end = 0, len(array)
  while start < end:
    mid = (start+end)//2
    if target==array[mid]:
      return mid
    elif target < array[mid]:
      end=mid
    else:
      start=mid+1

 

값을 찾았을때 값(mid)를 리턴하는 과정(target==array[mid])을 없애버리고 조금 수정해주었다.

 

(Lower Bound)

def lowerbound(array, target):
  start, end = 0, len(array)
  while start < end:
    mid = (start+end)//2
    if target <= array[mid]:
      end=mid
    else:
      start=mid+1
  return start

 

(Upper Bound)

def upperbound(array, target):
  start, end = 0, len(array)
  while start < end:
    mid = (start+end)//2
    if target < array[mid]:
      end=mid
    else:
      start=mid+1
  return start-1

 

✏️ 파이썬 라이브러리 bisect

파이썬엔 웬만한건 다 구현되어있다. upper, lower bound도 마찬가지다.

• bisect_left(literable, value) : 같을 경우 왼쪽 인덱스 구하기
• bisect_right(literable, value) : 같을 경우 오른쪽 인덱스 구하기

from bisect import bisect_left, bisect_right 
nums = [0,1,2,3,4,5,6,7,8,9] 
n = 5 

print(bisect_left(nums, n)) 
print(bisect_right(nums, n)) 

''' 
결과값 
5 
6 
'''

 

from bisect import bisect_left, bisect_right


dp=[1,5,10]
print(bisect_left(dp, 6))
print(bisect_right(dp, 6))

print(bisect_left(dp, 5))
print(bisect_right(dp, 5))