Lower 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]
print(binarySearch(0, len(lst)-1, 7))

 

 

Lower bound 이진 탐색이란 

찾고 싶은 key 값과 같은 값이 나타나는 첫 위치를  찾거나,

같은 값이 없으면 큰 값이 나타나는 첫 위치를 찾는 방법이다.

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

범위 설정에 있어서 이진 탐색과 비교했을 때 이해가 안되서 애먹었다.

일부러 이해하기 쉽도록 ==, <, > 세 가지 케이스로 나누었다.

 

먼저 2번째 줄, 보통의 이진 탐색은 조건을 while start <= end 로 잡는다.

하지만 lower bound는 while start < end 로 잡는다.

그 이유는 일반 이진 탐색은 start == end가 되었을 때도 그 값이 찾고자 하는 key였는지 살피고 나서 찾았으면 1을 리턴하고 못 찾았으면 0을 리턴하든지 해야 하는데,

lower bound는 start == end가 되었으면 바로 그 위치를 리턴하면 되기 때문이다. start == end가 되는 순간 그 값이 key와 같은 값이거나 처음으로 큰 것이 나타나는 위치이기 때문이다. 그래서 start == end 는 while이 진행될 조건으로 포함시킬 필요가 없다.

 

다음 if 문을 보자.

일반 이진 탐색에서의 세 가지 if문을 보자.

1. lst[mid] == key

2. key < lst[mid]

3. lst[mid] < key

 

먼저 3번은 일반 이진 탐색과 같다고 보면 된다. 

lower bound는 key와 같거나 더 큰 값을 찾아야 하므로 key가 더 크다면 start를 높여서 최소한 같은 값이라도 찾을 수 있도록 범위를 좁혀주어야 한다.

하지만 1. lst[mid] == key 일 때는?

원하는 key가 나오긴 했지만, 똑같은 값이 더 왼쪽에서 나타날 수도 있다.

따라서 이 위치를 포함해서 더 작은 위치에서 이 값이 등장하지는 않는지 다시 한번 살펴야 하는 것이다.

2. key < lst[mid]도 마찬가지이다. key가 lst[mid]보다 작긴 하지만, 무작정 바이너리 서치처럼 end = mid - 1 할 수 없는 이유는 lst[mid]가 key보다 처음으로 큰 값일 수 있기 때문이다.

 

마지막, lowerBound 함수를 호출하는 부분을 보자.

보통 이진 탐색이라면 함수를 호출할 때 start를 0으로, end를 len(lst)-1로 둘 것이다. 왜냐? 배열은 0부터 시작이니까.

하지만 lower bound 이진 탐색의 경우, end를 len(lst)로 두었다.

그 이유는 리스트 안에 원하는 값이 없었을 경우, 즉 원하는 key보다 작은 값들만 있었을 경우 

마지막 while문을 돌 때 start와 end가 len(lst)가 됨으로써

len(lst)를 반환하게 되고, 리스트에 존재하지 않는 인덱스를 반환했기 때문에 리스트에 key가 없다! 는 것을 알기 위함이다.

(원하는 key보다 큰 값들만 있었을 경우에 리턴값은 0이다. lower bound가 뭔지 생각해보자)