Binary search, 이진 탐색

이진 탐색에 대해 공부하였다.

 

파이썬의 리스트 자료구조에서, for문을 통해 첫번째 인덱스부터 마지막 인덱스까지 순차적으로 탐색을 하였다가는

시간 복잡도 문제를 문제를 벗어날 수 없게 된다.

이러한 문제를 해결하기 위하여, 이진 탐색 아이디어를 활용할 수 있다.

 

이진 탐색

 

이진 탐색이란, 리스트를 절반으로 쪼개어 탐색하는 과정이다.

 

0 1 2 3 4 5 6 7 8 9 라는 리스트가 있다고 할 때에,

찾고자 하는 수가 0~4와 5~9 중 어디에 있는 지를 파악하고,

만약 전자의 범위 내에 있다면 전자의 범위에서, 그 반대라면 후자의 범위 내에서 탐색하는 방법이다.

 

이러한 이진 탐색을 구현하는 방법은 두 가지 방법이 있는데,

하나는 재귀 함수를 이용하는 방법이고, 다른 하나는 반복문을 사용하는 방법이 있다.

 

재귀함수 이용

def binary_search(array,target,start,end):
    if start > end:
        return None
    mid = (start + end) // 2
    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binary_search(array,target,start,mid-1)
    else:
        return binary_search(array,target,mid+1,end)

파라미터 값을 바꿔 입력하며 해당 값을 찾거나, 혹은 해당 값이 배열 내에 없는 것을 확일할 때 까지 함수를 반복 호출한다.

파이썬에서의 재귀함수 깊이 제한은 256회니, 최악의 경우에도 리스트 길이가 약 2의 255~256제곱까지는 감당 가능할 것으로 보인다.

 

반복문 이용

def binary_search(array,target,start,end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None

바뀐 것은 재귀함수 대신 while 반복문을 사용하였다는 것이다.

 

파이썬에서 count 메서드를 이용하게 된다면, 순차탐색이 이루어지게 되므로 log(N)의 시간복잡도를 갖게 된다.

하지만 위의 이진 탐색 방법을 사용하게 된다면, log(N) 보다 낮은 시간복잡도 내에서 탐색을 실시할 수 있게 된다.