파이썬 이진 탐색

이진탐색이란? (What is binary search?)

  정렬된 수열에서 특정 값을 찾고자 할때 여러가지 검색 알고리즘들이 사용될 수 있습니다. 그 중 가장 손쉽게 구현 및 사용이 가능한 알고리즘이 바로 이진탐색 알고리즘 입니다. 이는 단순히 수열에서뿐만 아니라 이진 탐색 트리에서도 사용되는 알고리즘이라고 볼 수 있습니다. 

 

이진탐색 검색의 동작 방법은 매우 간단합니다. 아래와 같이 [2, 4, 5, 9, 11, 24, 70, 101]의 수열이 있다고 가정합니다. 이 때 여기서 '5'라는 숫자값이 존재하는지 여부를 찾고 싶습니다. 

최초 검색은 전체 수열의 중간 값이 찾고자 하는 값과 동일한지를 비교한 것 입니다. 즉, 탐색 범위는 아래에서 노란색으로 표시된 구역이며, 이 구역의 가운데 위치의 값이 찾고자 하는 값인지를 비교합니다. 처음에는 11과 5를 비교합니다.

 

그런데 11이라는 값은 찾고자 하는 값인 5보다 큰 값 입니다. 즉, 원하는 값을 찾지는 못했으나 앞으로 값을 찾아야 하는 범위가 11의 좌측 위치가 되어야 한다는 것을 쉽게 알 수 있습니다. 이에 우리는 찾고자 하는 범위를 11의 좌측으로 옮깁니다. 이에 새롭게 탐색을 수행하는 범위는 아래와 같아집니다. 

 

탐색하는 범위 내 중간값이 target 값인지를 살펴봅니다. 

 

이번에는 찾고자 하는 값인 5보다 작은 값입니다. 이제 찾아야 하는 범위를 현재 값의 우측으로 줄입니다. 

 

줄어든 범위 내에서 중간 (2개 밖에 없기에 첫 번째 것 선택)의 값과 찾고자 하는 값이 같은지를 비교합니다. 

 

  네, 현재 값이 찾고자 하는 값와 동일합니다. 이렇게 하나의 수열 내에서 원하는 값을 찾게 되었으며, 값을 찾기까지 수행된 연산 횟수는 3번 입니다. 전체 수열의 길이가 8인데, 3번만에 원하는 값을 찾을 수 있었던 것 입니다. 각각의 찾기 연산에서 전체 길이를 1/N로 계속 줄여나가기에 평균적으로 탐색에 소모되는 시간은 O(log N) 입니다. 위의 경우 log 8 = 3이니 정확히 평균의 시간이 걸리는 case 라고 할 수 있겠습니다. 

 

Python으로 binary search는 다음과 같이 구현될 수 있습니다. 

def search_binary(arr, left, right, key):
   while left <= right:
       mid = (left + right) // 2
       if arr[mid] == key:
           return mid
       if key > a[mid]:
           left = mid + 1
       else:
           right = mid - 1
   return -1

  위 binary search 함수는 4개의 인자를 받습니다. 첫 번째는 정렬된 원소들을 지니고 있는 배열 arr 이며, 두 번째는 arr에서 유효한 원소가 시작되는 위치 left, 그리고 세 번째는 arr에서 유효한 원소가 끝나는 위치인 right, 그리고 마지막으로 arr에서 찾고자 하는 target 값인 key 입니다. 

 

앞서 살펴봤던 example의 경우 arr는 [2, 4, 5, 9, 11, 24, 70, 101]이 되며, left와 right는 모두 0, 그리고 key는 5가 됩니다. 즉, 다음과 같이 위 함수가 호출되게 됩니다.

arr = [2, 4, 5, 9, 11, 24, 70, 101]
search_bniary(arr, 0, len(arr) - 1, 5)

while loop 의 최초 실행 시, left는 0, right는 7입니다. 즉, mid는 3이 되기에 배열 내 4번째 요소인 9와 key인 5를 비교하게 됩니다. 9가 5보다 크기에 right를 mid 값 - 1의 값으로 할당합니다.

이제 두 번째 loop에서 left는 0, right는 2 입니다. mid는 1이므로, 4와 5를 비교합니다. 4가 5보다 작기에 left를 mid + 1의 값으로 할당합니다.

left는 2, right도 2입니다. mid는 2이므로, arr의 5와 key 5를 비교합니다. 이 둘은 값이 같기에 찾은 위치인 2를 리턴합니다.