Upper bound 이진 탐색

앞서 Lower bound 이진 탐색에 대해 알아보았다. 

https://awesomeroo.tistory.com/30

 

 

이번에는 Upper bound 이진 탐색이다. Upper bound 이진 탐색은 처음으로 큰 값이 나타나는 위치를 찾는다.

먼저 일반적인 binary search 코드이다.

Lower bound에서도 그랬지만, Upper bound와의 코드 비교를 위해서 올린다.

def binarySearch(start, end, key):
    while start <= end:
        mid = (start + end) // 2
        if lst[mid] > key:
            end = mid - 1
        elif lst[mid] < key:
            start = mid + 1
        elif lst[mid] == key:
            return 1
    return 0


lst = [0, 1, 2, 3, 3, 5, 6, 7, 8]
print(binarySearch(0, len(lst)-1, 3))

 

 

그리고 Upper bound binary search.

def upperBound(start, end, key):
    while start < end:
        mid = (start + end) // 2
        if lst[mid] == key:
            start = mid + 1
        elif lst[mid] < key:
            start = mid + 1
        elif key < lst[mid]:
            end = mid
    return end
    
lst = [0, 1, 2, 3, 3, 5, 6, 7, 8]
print(upperBound(0, len(lst), 6))

 

이번에도 upper bound에서는 일반 바이너리 서치와 같은 세 가지 if문이 등장한다.

1. lst[mid] == key

2. lst[mid] < key

3. key < lst[mid]

 

먼저 1번을 보자. upper bound는 key보다 큰 값이 나오는 위치를 찾아야 하므로, 

lst[mid]가 key와 같다면 그 값은 포함시킬 필요가 없다. 따라서 start를 mid에서 하나 증가한 값으로 변경한다.

2번. key가 lst[mid]보다 크다면, 마찬가지로 key보다 큰 값을 찾아야 하기 때문에 key보다 작은 lst[mid]는 다음 탐색 범위에 포함시킬 필요가 없다. 그래서 start를 mid에서 하나 증가한 값으로 변경한다.

3번. key가 lst[mid]보다 작을 때를 보자. mid가 너무 큰 것이므로 end를 작게 해줘야 하는데, lst[mid]가 key보다 처음으로 큰 값(원하는 값)일 수도 있으므로 lst[mid]를 포함시키기 위해 end=mid가 된다.

 

return end 하는 이유는, start = end가 되는 순간 start와 end가 정답이 되기 때문이다.

 

또한 함수를 처음 콜하는 부분에서 end가 len(lst)-1이 아니라 len(lst)가 되는 이유는,

리스트를 끝까지 살폈는데 답이 안 나온다면 마지막으로 살폈던 위치를 반환할 것이기 때문이다. 그 때 len(lst)를 반환해서 답이 없음을 알아보기 위함이다.