먼저 이진 탐색 코드.
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가 뭔지 생각해보자)
'알고리즘 > 바이너리서치' 카테고리의 다른 글
| 10816번. 숫자카드 2 (0) | 2019.12.12 |
|---|---|
| Upper bound 이진 탐색 (0) | 2019.12.12 |
| 1920번. 수 찾기 (0) | 2019.12.10 |