[이진탐색] lower bound 찾기

기본적인 이진탐색

• 목적
  이분 탐색하면서 target값 찾기

def binary_search(array, target):
	lower = 0
    upper = len(array)
    while lower<=upper:
    mid=(lower+upper)//2
    if array[mid]>target:
    	upper = mid-1
    elif array[mid]<target:
    	lower = mid+1
    else:
    	return mid
   return -1

lower bound 찾기

• lower bound
  target과 값이 같거나 큰 값이 최초 등장하는 인덱스
  

목적
lower bound 찾기

a = [1,2,2,3,3,3,4,6,7]
b = [1,2,3,4,5,6,7]

def lower_bound(array, target):
  lower = 0
  upper = len(array)
  while lower < upper:
    mid = (lower+upper)//2
    if mid>=target:
      upper = mid
    else:
      lower = mid+1
  return lower, upper

def lower_bound_j(array, target):
  lower = 0
  upper = len(array)
  while lower < upper:
    mid = (lower+upper)//2
    if mid>=target:
      upper = mid-1
    else:
      lower = mid+1
  return lower, upper

print(lower_bound(a, 3), lower_bound_j(a, 3))
print(lower_bound(b, 3), lower_bound_j(b, 3))

lower bound 이진탐색 함수는 위의 lower_bound함수이다.

그런데 왜 upper = mid여야 하는지 이해가 안됐다.

(3, 3) (3, 3)
(3, 3) (2, 2)

a array일 경우에는 mid-1로 해도 결과가 같다.
b array일 경우에는 mid-1로 할 경우 틀린 결과가 나온다.

위의 과정때문에 그렇게된다.

mid가 탐색 범위에 포함되어야 마지막에 lower=upper가 돼서 탐색이 끝날때 mid가 들어갈 수 있다.