서론
주어진 리스트에서 어떤 key 값을 찾아야 할 때,
만약 리스트가 정렬이 되어있다면 이진 탐색이 유리하고
정렬되지 않은 리스트라면 어쩔 수 없이 리스트의 처음부터 끝까지 하나하나 살펴봐야한다. 이 방법은 순차 탐색이라고 한다.
이진 탐색은 무엇일까? 이번 포스팅에서는 파이썬으로 이진 탐색을 구현해보려고 한다.
이진 탐색이란?
이진 탐색(Binary search)은 정렬된 리스트가 주어졌을 때 사용하는 탐색 방법이다.
이런 정렬된 리스트가 주어지고, 이 중에서 18을 찾아보려고 한다.
이진 탐색은 이 리스트의 가운데를 먼저 본다.
리스트의 가운데는 25다. 우리가 찾고자 하는 수는 25보다 작다.
리스트가 이미 정렬이 되어있으므로 25 이후(오른쪽)의 숫자를 볼 필요가 없다. 이제 25의 왼쪽 숫자들만 볼 것이다.
여기까지가 이분 탐색의 첫번째 단계다.
이제 다시 이 과정을 반복한다.
왼쪽에서 가운데는 13이다. 13과 18을 비교한다.
18이 더 크므로 이제 오른쪽만 본다.
다시 나눈다.
이번에는 가운데 숫자가 18이다.
우리가 찾던 숫자가 나왔으므로 해당 숫자의 인덱스를 돌려준다.
만약 이렇게 계속 나누어서 더이상 나눌 수가 없는데도 여전히 답이 나오지 않았다면 그건 해당 숫자가 리스트에 없는 것이다.
이분 탐색을 분할 정복법으로 구현
이번 포스팅에서는 이분 탐색을 분할 정복(Divide and Conquer)법으로 구현해볼 것이다.
- 리스트 S의 가운데 원소와 key를 비교하여 같으면 해당 위치를 리턴한다. 아니면,
- [Divide] 가운데 원소를 기준으로 S를 두 개의 리스트로 분할
- [Conquer] key가 가운데 원소보다 크면 오른쪽, 작으면 왼쪽을 재귀 호출
- [Obtain] 선택한 리스트에서 얻은 답을 리턴
def BS_recursive(S, low, high):
if (low > high): # 종료조건 : 못 찾은 경우
return -1 # index로 -1 리턴
else:
mid = (low + high) // 2
if key == S[mid]:
return mid
elif key < S[mid]:
return BS_recursive(S, low, mid - 1)
else:
return BS_recursive(S, mid + 1, high)
S = [-1, 10, 12, 13, 14, 18, 20, 25, 27, 30, 35, 40, 45]
key = 18
loc = BS_recursive(S, 0, len(S)-1)
print('S :', S)
print('key :', key)
print('loc =',loc)
