이분탐색 Lower Bound와 Upper Bound

• 정렬된 리스트에서 k가 들어갈 적절한 위치를 찾고 싶습니다.
• 단, 리스트에는 k가 존재할 수도 있고 없을 수도 있습니다.
• 따라서 이 경우, 이진탐색(=정렬된 데이터에서 k를 정확하게 찾는 알고리즘)을 조금 변형한 lower bound 또는 upper bound 알고리즘을 사용해야 합니다.

Lower Bound

• k '이상'이 처음 나오는 위치입니다.

Upper Bound

• k를 '초과'한 값이 처음 나오는 위치입니다.

---

예시

다음과 같은 정렬된 리스트가 있습니다. k = 4 입니다.

값	0	1	2	4	4	4	7	8
위치(index)	0	1	2	3	4	5	6	7

ⓐ lower bound?

• k(=4) 이상의 값이 처음 나오는 위치를 찾습니다.
• lower bound는 index = 3 입니다.

ⓑ upper bound?

• k(=4) 초과의 값이 처음 나오는 위치를 찾습니다.
• upper bound는 index = 6 입니다.

---

파이썬으로 구현해봅시다

ⓐ lower bound

def lowerbound(array, k):
    left = 0
    right = len(array)

    while left < right:
        mid = (left + right) // 2

		# 📢 이 부분 주의!
        if array[mid] >= k:
            right = mid
        else:
            left = mid + 1

    return left

ⓑ upper bound

def upperbound(array, k):
    left = 0
    right = len(array)
    
    while left < right:
        mid = (left + right) // 2
		
        # 📢 이 부분 주의!
        if array[mid] <= k:
            left = mid + 1
        else:
            right = mid

    return left  

---

참고로...

• 파이썬에는 bisect라는 라이브러리가 존재합니다.
• bisect_left(iterable, k) : lower bound와 동일합니다.
• bisect_right(iterable, k) : upper bound와 동일합니다.