Leon Chaewon Kong's dev blog

파이썬 이진탐색 알고리즘

11 Dec 2018

이진탐색

이진탐색이란 정렬된 리스트에서 타겟을 효율적으로 찾는 알고리즘이다. 먼저 주어진 리스트를 절반으로 나누고, 타겟이 앞 절반 리스트에 속하는지 뒷 절반 리스트에 속하는지 파악한다. 만약 앞에 속한다면 뒤의 리스트는 버리고 앞의 리스트를 택하며, 반대일 경우 뒤의 리스트를 택한다. 그리고, 다시 택한 리스트를 반으로 나눠 앞서 진행한 조사를 반복한다. 리스트의 크기를 절반씩 좁혀가며 타겟이 위치한 리스트를 찾아나가는 것이 이진 탐색의 핵심이다.

이진탐색의 전제는 정렬된 리스트이다. 정렬되지 않은 리스트에 대해서는 정렬작업을 먼저 선행해야 한다. 그렇지 않고서는 이진탐색을 할 수 없다. 그렇다면 이런 한계가 있음에도 이진탐색을 사용하는 이유는 무엇일까?

사전을 예로 들어보자. 영한사전에서 완전탐색 방식으로 ‘toxic’을 찾는다고 해보자. 만약 ‘toxic’의 위치가 22,109번째이고, 총 단어의 개수가 3만 개라면, 22,109번의 비교를 해야만 ‘toxic’의 위치를 찾을 수 있다.

반면, 이진 탐색을 사용하면,

  1. toxic의 인덱스 = 22,109 > 15,000 이므로 15,000 ~ 30,000 구간을 탐색
  2. 22,500보다 작으므로 15,000 ~ 22,500 구간을 탐색
  3. 18,750보다 크므로 18,750 ~ 22,500 구간을 탐색
  4. 20,625보다 크므로 20,625 ~ 22,500 구간을 탐색
  5. 21,562보다 크므로 21,562 ~ 22,500 구간을 탐색
  6. 22,031보다 크므로 22,031 ~ 22,500 구간을 탐색
  7. 22,265보다 작으므로 22,031 ~ 22, 265 구간을 탐색
  8. 22,148보다 작으므로 22,031 ~ 22,148 구간을 탐색
  9. 22089보다 크므로 22,089 ~ 22,148 구간을 탐색
  10. 22,118보다 작으므로 22,089 ~ 22,118 구간을 탐색
  11. 22,103보다 크므로 22,103 ~ 22,118 구간을 탐색
  12. 22,110보다 작으므로 22,103 ~ 22,110 구간을 탐색
  13. 22,106보다 크므로 22,106 ~ 22,110 구간을 탐색
  14. 22,108보다 크므로 22,108 ~ 22,110 구간을 탐색
  15. 22,109 발견 및 탐색 종료

22,109번을 비교해야 발견할 수 있었던 ‘toxic’ 단어를 불과 15번의 탐색 작업 만으로도 발견할 수 있었다. 이것이 이진탐색의 강력함이다.

파이썬으로 이진탐색 구현하기

파이썬으로 이진탐색 함수를 구현하면 다음과 같다.

def binary_search(arr, target):

    def search(start, end):
        mid = (start + end) // 2
        if start == end:
            return -1 if arr[start] != target else start
        elif target > arr[mid]:
            return search(mid+1, end)
        else:
            return search(start, mid)
    
    return search(0, len(arr) -1)

차근차근 살펴보자

arr, target

arr은 정렬된 리스트, target은 찾으려는 대상을 의미한다.

def search(start, end):
    mid = (start + end) // 2

search 함수는 탐색의 대상이 되는 배열의 시작 인덱스와 끝 인덱스를 인자로 받는다

중간 값을 구해 리스트를 중심을 기준으로 2개의 리스트로 분할하는 작업을 할 것이다.

if start == end:
    return -1 if arr[start] != target else start

위 코드는 종료조건을 명시한다.

만약 start와 end가 같게 되면 리스트의 길이가 1, 즉 1개의 원소만 있게 되므로 값을 비교하고 맞으면 인덱스를, 틀리면 -1을 반환한다.

elif target > arr[mid]:
    return search(mid+1, end)
else:
    return search(start, mid)

위 코드가 바로 arr리스트를 재귀호출을 통해 계속 반씩 쪼개 나가며 탐색을 하도록 하는 코드이다.

먼저 target이 mid 인덱스의 숫자보다 작은지, 크거나 같은지를 확인한다. 만약 target이 arr[mid] 보다 크다면, mid+1부터 end 까지만 탐색하면 된다. 정렬된 리스트이기 때문에 mid보다 작은 인덱스를 가지는 숫자들은 전부 arr[mid]보다는 작기 때문이다.

반대로, arr[mid]와 target이 작거나 같다면, start에서 mid까지만 탐색하면 된다.

재귀호출을 통해

return search(0, len(arr) -1)

마지막으로 search라는 함수를 실행하는 코드이다. start에는 0을, end에는 arr의 마지막 element의 인덱스이기도 한 len(arr)-1을 넣는다.

# 예제 확인
arr = [1, 3, 5, 7, 9]
target1 = 4
target2 = 9
print(binary_search(arr, target1))
## -1
print(binary_search(arr, target2))
## 4

이진탐색이 정상적으로 작동함을 확인할 수 있다.

마치며

이진탐색을 활용하면 완전탐색보다 훨씬 효율적으로 정렬된 리스트에서 목표값(target)을 찾아나갈 수 있다.

그러나, 완전탐색이 경우에 따라서는 이진탐색보다 유리할 수도 있다. 이진탐색은 앞서 말했듯, 정렬된 리스트를 대상으로만 작동한다. 따라서 정렬되지 않은 리스트를 탐색해야할 경우, 정렬을 실시해야 한다.

정렬 알고리즘은 최선이 O(nlogn)이다. 만약 리스트의 길이가 짧다면 구현하기도 간단하고 탐색의 시간복잡도가 O(n)인 완전탐색이 유리할 수도 있는 것이다.

Related Posts