파이썬 이진 탐색

이진탐색이란? (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(a, left, right, key):
   while left <= right:
       mid = (left + right) // 2
       if a[mid] == key:
           return mid
       if key > a[mid]:
           left = mid + 1
       else:
           right = mid - 1
   return -1