1. 이분 탐색이란?
정렬되어 있는 범위에서 원하는 값을 찾기 위해 반씩 줄여가며 탐색하는 알고리즘입니다.
정렬만 되어 있다면, 선형적으로 다 탐색할 필요 없이 범위가 반씩 줄어들기 때문에 시간복잡도가 \(O(\log{n})\)으로 상당히 효율적인 알고리즘입니다.
영어로 Binary Search입니다.
Binary라는 단어가 한국어로 번역되면서 이진 탐색, 이진 검색 등으로 사용됩니다.
하지만 탐색 과정을 살펴보면 범위를 반으로 쪼개며 진행되기 때문에 이분 탐색이라는 용어가 더 직관적인 것 같습니다.
https://ko.wikipedia.org/wiki/이진_검색_알고리즘
이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여,
ko.wikipedia.org
2. 이분 탐색 과정 살펴보기
일반적인 이분 탐색의 과정을 살펴봅시다.
위의 썸네일과 같은 숫자 배열이 있을 때, 28을 찾아봅시다.
먼저, 주어진 범위 양쪽 끝에서 가운데를 찾습니다.(다행이 이 경우 개수가 홀수라 정가운데가 있습니다.)
가운데 값이 28보다 크므로 가운데를 포함한 오른쪽 범위는 버립니다.
그리고 오른쪽 화살표를 가운데의 왼쪽 자리로 가져옵니다.
줄어든 범위에서 가운데를 찾습니다.
범위가 4로 짝수이므로 가운데가 애매합니다.
보통 연산을 편하게 하기 위해 2로 나누어 나머지를 버리면 가운데 두 개 중 왼쪽이 선택됩니다.
그렇게 선택된 8은 28보다 작으므로 가운데를 포함한 왼쪽을 버립니다.
그리고 왼쪽 화살표를 가운데의 오른쪽 자리로 가져옵니다.
이제는 범위가 2입니다.
엄밀히 따져보면 가운데가 없으므로 찾는 값은 범위의 둘 중 하나입니다.
하지만 간결한 코드를 위해 위의 과정을 한 번 더 거칩니다.
이제는 가운데 값이 왼쪽 값과 같습니다.(2로 나누어 나머지를 버렸기 때문에)
가운데 값 20은 28보다 작으므로 가운데 값을 포함한 왼쪽을 버립니다.(범위가 작아 20만 버려집니다.)
왼쪽 화살표를 가운데의 오른쪽 자리로 가져옵니다.
이제 범위는 1이고, 엄밀히 한 값을 가르키고 있습니다.
가운데 값 또한 같은 값을 가르키게 되고, 가운데 값이 28이므로 현재 가운데 값의 인덱스인 3을 출력합니다.
만약 이 과정을 모두 거쳤는데 우리가 원하는 값이 없을 경우는 어떻게 될까요?
예를 들어 27이나 29를 찾는 경우를 생각해봅시다.
마지막 단계에서도 원하는 값을 찾지 못했기 때문에 왼쪽 또는 오른쪽 화살표를 한 번 더 옮기게 됩니다.
결국 왼쪽과 오른쪽 화살표가 자리를 바꾸게 되면서(왼쪽 화살표의 인덱스가 오른쪽 화살표의 인덱스보다 커지면서) 제외했던 범위로 화살표가 들어가게 됩니다.
따라서 왼쪽과 오른쪽 화살표가 자리가 바뀌게 되는 상황에서 탈출 조건을 만들면 됩니다.
지금까지의 과정(일반적인 이분 탐색)을 코드로 나타내면 다음과 같습니다.
nums = [5, 8, 20, 28, 44, 66, 81, 92, 99]
def binary_search(target):
l, r = 0, len(nums)-1
while l <= r: # 왼쪽과 오른쪽 화살표가 자리가 바뀔 때까지 반복
m = (l+r)//2
# 범위가 너무 클 때 overflow를 방지하려면 l + (r-l)//2
if nums[m] == target:
return m
if nums[m] < target:
l = m+1
else:
r = m-1
return "Search Fail!"
print(binary_search(28))
# 3
print(binary_search(27))
# Search Fail!
print(binary_search(29))
# Search Fail!
3. 탐색을 실패해도 마지막 탐색한 값(오른쪽 자리)을 출력하기
원하는 값이 배열에 없는 경우 탐색을 실패하지만, 마지막까지 탐색한 값은 의미가 있습니다.
바로 우리가 원하는 값과 아주 가까운 값이기 때문입니다.
따라서 탐색을 실패했을 때 마지막까지 탐색한 값을 출력해봅시다.
위에서 살펴본 것처럼 배열에 없는 값인 27이나 29를 탐색해도 결국 28까지 탐색하게 됩니다.
우리는 이 상황이 더 이상 탐색할 범위가 없다는 것(범위가 1)을 알고 있습니다.
하지만 위에서 보면 한 번 더 탐색해서 결국 왼쪽 화살표와 오른쪽 화살표가 자리를 바꾸게 되면서 탐색 실패로 연결됩니다.
그렇다면 한 번 더 탐색을 막기 위해서는 마지막 탈출 조건을 조금만 바꾸어 주면 됩니다.
두 화살표가 자리를 바꾸는 순간이 아니라 같은 값을 가르킬 때 탈출시키면 됩니다.
하지만 두 가지 문제가 있습니다.
먼저, 20을 탐색한다고 하면 위 상황에서 어떻게 될까요?
왼쪽 화살표와 오른쪽 화살표가 하나로 합쳐지기 전에 가운데 값이 우리가 찾는 값입니다.
원래대로면 탈출시켜야하지만, 코드의 간결성을 위해 생각해봅시다.
범위가 2일 때 가운데는 왼쪽(나머지를 버림)을 선택하므로 가운데 값과 찾는 값이 같을 경우에는 오른쪽 화살표를 옮기면 됩니다.
정리하면, 가운데 값 < 찾는 값 일 때는 왼쪽 화살표를, 가운데 값 >= 찾는 값 일 때는 오른쪽 화살표를 옮기면 됩니다.
다음으로, 19를 탐색한다고 하면 위 상황에서 어떻게 될까요?
오른쪽 화살표가 왼쪽 화살표와 같은 위치로 가질 않고, 가운데 화살표 왼쪽으로 옮겨가면서 곧바로 왼쪽 화살표와 오른쪽 화살표의 자리가 바뀌게 됩니다.
이런 일이 일어나는 이유는 범위가 짝수일 때 중간값을 왼쪽(나머지를 버림)으로 선택하기 때문에 생깁니다.
따라서 오른쪽 화살표는 가운데 화살표의 왼쪽으로 넘기는게 아니라 가운데 화살표가 가르키는 방향으로 옮겨주면 됩니다.
그림으로 27과 29를 이분탐색하는 과정을 보면 위와 같습니다.
찾는 값이 없다면 찾는 값의 오른쪽 자리를 출력하는 것을 볼 수 있습니다.
코드는 다음과 같습니다.
nums = [5, 8, 20, 28, 44, 66, 81, 92, 99]
def binary_search(target):
l, r = 0, len(nums)-1
while l < r: # 왼쪽과 오른쪽 화살표가 겹칠 때까지 반복
m = (l+r)//2
# 범위가 너무 클 때 overflow를 방지하려면 l + (r-l)//2
if nums[m] < target:
l = m+1
else:
r = m # 오른쪽 화살표를 가운데 값의 왼쪽으로 넘기지 않음
return r
print(binary_search(28))
# 3
print(binary_search(27))
# 3
print(binary_search(29))
# 4
4. 탐색을 실패했을 때 왼쪽 자리를 출력하기
위에서 보면 탐색을 실패했을 때 무조건 오른쪽 자리를 출력하게 됩니다.
20과 28 사이의 수를 탐색하면 마지막 순간에 위와 같이 될 것입니다.
우리는 가운데 값을 나머지를 버림으로 계산하고, 결국 왼쪽 값(더 작은 값)이 가운데로 선택되게 됩니다.
결과적으로 왼쪽 화살표가 오른쪽 화살표 쪽으로 움직이고, 찾는 값의 오른쪽을 가리키며 탐색이 종료됩니다.
만약 찾는 값의 왼쪽을 찾으려면 어떻게 해야할까요?
오른쪽을 나타내게 되는 이유가 범위가 짝수일 때 왼쪽 값을 선택(나머지를 버림)하기 때문입니다.
따라서 왼쪽을 찾으려면 범위가 짝수일 때 오른쪽 값을 선택(나머지를 올림)하면 됩니다.
이때 주의할 점은, 이제는 왼쪽 화살표를 가운데 값으로 옮겨야하고 오른쪽 화살표는 가운데에서 바로 왼쪽으로 옮겨야한다는 점입니다.
그리고 가운데 값이 찾는 값일 때에도 오른쪽 화살표가 아닌 왼쪽 화살표를 옮겨야합니다.
정리하면, 가운데 값 <= 찾는 값 일 때는 왼쪽 화살표를, 가운데 값 > 찾는 값 일 때는 오른쪽 화살표를 옮기면 됩니다.
27과 29를 탐색하는 과정은 위와 같습니다.
그리고 코드는 다음과 같습니다.
nums = [5, 8, 20, 28, 44, 66, 81, 92, 99]
def binary_search(target):
l, r = 0, len(nums)-1
while l < r: # 왼쪽과 오른쪽 화살표가 겹칠 때까지 반복
m = (l+r+1)//2
# 범위가 너무 클 때 overflow를 방지하려면 l + (r-l+1)//2
if nums[m] <= target:
l = m # 왼쪽 화살표를 가운데 값의 오른쪽으로 넘기지 않음
else:
r = m-1
return r
print(binary_search(28))
# 3
print(binary_search(27))
# 2
print(binary_search(29))
# 3
5. 찾는 값이 여러 개일 때 결과 조절하기(Upper Bound, Lower Bound)
위의 배열에서 28을 세 개로 늘려봅시다.
이제 28을 탐색하려고 할 때, 어떤 값을 출력해야 될까요?
아마도 의미있는 값은 네 가지 일 것입니다.
1 - 첫 번째 28이 시작되기 전 인덱스
2 - 첫 번째 28의 인덱스
3 - 마지막 28의 인덱스
4 - 마지막 28의 다음 인덱스
결론부터 말하자면 이 네 가지 결과값을 모두 출력할 수 있습니다.
먼저, 앞에서 살펴본 실패해도 오른쪽 자리를 출력하는 이분 탐색을 실행해서 28을 찾으면 어떻게 될까요?
위 과정을 따라서 첫 번째 28의 인덱스가 출력됩니다.
범위가 줄어드는 과정을 살펴보면, 원하는 28을 찾았지만 범위가 1이 아니기 때문에 탐색은 계속됩니다.
앞에서 살펴본 것처럼 가운데 값이 원하는 값보다 크거나 같으면 오른쪽 화살표를 옮겨옵니다.
따라서 28 중에 가장 왼쪽에 있는 28을 향해 범위가 줄어듭니다.
이것을 Lower Bound라고 하고, 중복된 수가 있을 때 왼쪽 경계를 찾는 일반적인 방법입니다.
nums = [5, 8, 20, 28, 28, 28, 81, 92, 99]
def binary_search(target):
l, r = 0, len(nums)-1
while l < r: # 왼쪽과 오른쪽 화살표가 겹칠 때까지 반복
m = (l+r)//2
# 범위가 너무 클 때 overflow를 방지하려면 l + (r-l)//2
if nums[m] < target: # 가운데 값이 작으면 왼쪽 화살표를 옮김
l = m+1
else: # 가운데 값이 크거나 '같으면' 오른쪽 화살표를 옮김(Lower Bound)
r = m
return r
print(binary_search(28))
# 3
그렇다면 오른쪽 경계를 찾으려면 어떻게 해야할까요?
답은 원하는 28을 찾았을 때 오른쪽 화살표가 아닌 왼쪽 화살표를 옮기는 것에 있습니다.
따라서 가운데 값이 원하는 값보다 작거나 같을 때 왼쪽 화살표를 옮기면 됩니다.
탐색 결과 마지막 28의 다음 인덱스가 출력됩니다.
이것을 Upper Bound라고 하고, 중복된 수가 있을 때 오른쪽 경계를 찾는 일반적인 방법입니다.
nums = [5, 8, 20, 28, 28, 28, 81, 92, 99]
def binary_search(target):
l, r = 0, len(nums)-1
while l < r: # 왼쪽과 오른쪽 화살표가 겹칠 때까지 반복
m = (l+r)//2
# 범위가 너무 클 때 overflow를 방지하려면 l + (r-l)//2
if nums[m] <= target: # 가운데 값이 작거나 '같으면' 왼쪽 화살표를 옮김(Upper Bound)
l = m+1
else: # 가운데 값이 크면 오른쪽 화살표를 옮김
r = m
return r
print(binary_search(28))
# 6
이제 앞에서 살펴본 네 가지 중 두 가지를 구현해보았습니다.
그럼 첫 번째 28의 이전 인덱스와 마지막 28의 인덱스는 어떻게 구할까요?
이것의 정답은 탐색이 실패했을 때 왼쪽 인덱스를 출력했던 방법에 있습니다.
그리고 그 핵심은 범위가 짝수일 때 왼쪽이 아니라 오른쪽을 선택하는 것입니다.
이제는 위에서 살펴본 것과 같이 가운데 값이 원하는 값일 때 오른쪽 화살표를 옮길지, 왼쪽 화살표를 옮길지만 정하면 Lower Bound, Upper Bound를 구현할 수 있습니다.
그림과 코드로 살펴보면 다음과 같습니다.
먼저 첫 번째 28의 이전 인덱스(Lower Bound)입니다.
nums = [5, 8, 20, 28, 28, 28, 81, 92, 99]
def binary_search(target):
l, r = 0, len(nums)-1
while l < r: # 왼쪽과 오른쪽 화살표가 겹칠 때까지 반복
m = (l+r+1)//2
# 범위가 너무 클 때 overflow를 방지하려면 l + (r-l+1)//2
if nums[m] < target: # 가운데 값이 작으면 왼쪽 화살표를 옮김
l = m
else: # 가운데 값이 크거나 '같으면' 오른쪽 화살표를 옮김(Lower Bound)
r = m-1
return r
print(binary_search(28))
# 2
마지막으로 마지막 28의 인덱스를 출력(Upper Bound)하는 방법입니다.
nums = [5, 8, 20, 28, 28, 28, 81, 92, 99]
def binary_search(target):
l, r = 0, len(nums)-1
while l < r: # 왼쪽과 오른쪽 화살표가 겹칠 때까지 반복
m = (l+r+1)//2
# 범위가 너무 클 때 overflow를 방지하려면 l + (r-l+1)//2
if nums[m] <= target: # 가운데 값이 작거나 '같으면' 왼쪽 화살표를 옮김(Upper Bound)
l = m
else: # 가운데 값이 크면 오른쪽 화살표를 옮김
r = m-1
return r
print(binary_search(28))
# 5
