[이진탐색] 하한선[Lower bound], 상한선[Upper bound]

개념

 

이진탐색의 상한선, 하한선은 이진탐색 알고리즘에서 약간 변경된 것이다.

중복된 자료가 있을 때 유용하게 사용된다. 

 

 

http://bajamircea.github.io/coding/cpp/2018/08/09/lower-bound.html

 

 

 

1. 하한선[Lower bound]

데이터내에서 원하는 값보다 '같거나 큰 값' 중에 가장 앞에 있는 원소의 위치를 리턴한다.

위 이미지에서 lower_bound(3)은 index 3이다.

 

2. 상한선[Upper bound]

데이터내에서 원하는 값보다 '큰 값' 중에 가장 앞에 있는 원소의 위치를 리턴한다.

위 이미지에서 upper_bound(3)은 index 6이다.

 

 

+ 만약 모든 데이터가 원하는 값보다 작을 경우?

데이터 범위밖의 값을 리턴해야 한다.

그래서 일반적인 이분탐색과 달리 high를 len(array)-1이 아니라 len(array)로 한다. 

 

 

http://bajamircea.github.io/coding/cpp/2018/08/09/lower-bound.html

 

 

---

 

​구현

 

 

# 이진탐색
def binary_search(array, target):
    low = 0
    high = len(array) - 1

    while low <= high:
        mid = (low + high) // 2

        if array[mid] == target:
            return mid

        elif array[mid] < target:
            low = mid + 1

        else:
            high = mid - 1

    return -1


# 하한선
def lower_bound(array, target):
    low = 0
    high = len(array)

    while low < high:
        mid = (low + high) // 2

        if array[mid] >= target:
            high = mid

        else:
            low = mid + 1

    return low


# 상한선
def upper_bound(array, target):
    low = 0
    high = len(array)

    while low < high:
        mid = (low + high) // 2

        if array[mid] <= target:
            low = mid + 1

        else:
            high = mid

    return low


li = [1, 2, 2, 3, 3, 3, 4, 6, 7]

print(binary_search(li, 3))
print(lower_bound(li, 3))
print(upper_bound(li, 3))

 

 

실행결과

 

4
3
6