[알고리즘] Binary Search(이진 탐색)(Python)

* 개요

Binary Search(이진 탐색)은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다. 또한 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다. 이진 탐색은 위치를 나타내는 변수 3개를 사용하는데, 탐색하고자 하는 범위의 시작점(start), 끝점(end), 그리고 중간점(mid)이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색 과정이다. 순차 탐색의 시간복잡도가 O(N)인 것에 비해, 이진 탐색의 시간복잡도는 O(logN)이다. 따라서 데이터의 양이 많은 경우에는 이진 탐색을 활용하는 것이 효율적이다. 이진 탐색은 재귀함수로 구현할 수도 있고 반복문으로도 구현할 수 있다. 두 코드를 작성했으니 서로 비교하며 이진 탐색에 대해 알아보자.

 

* 파이썬으로 구현한 Binary Search(재귀)

재귀함수로 이진 탐색을 구현해보았다.

import sys

sys.setrecursionlimit(10 ** 5)

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)

array = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
length = len(array)
target = int(sys.stdin.readline())

result = binary_search(array, target, 0, length - 1)

if result is None :
    print("결과가 존재하지 않습니다.")

else :
    print(f"{result + 1}번째 순서에서 결과를 찾았습니다.")

우선 sys 모듈의 setrecursionlimit() 함수로 재귀의 깊이를 설정하였다.

array를 먼저 살펴보면 0, 2, 4, 6, 8, 10, 12, 14, 16, 18의 데이터가 존재한다.

시작점의 인덱스는 0, 끝점의 인덱스는 9이다. 그렇다면 중간점은 (0 + 9) // 2 -> 4가 될 것이다.

시작점과 끝점, 중간점을 모두 구했으니 이진 탐색(binary_search)을 진행하면, 시작점이 끝점보다 클 경우 None을 반환하고 함수를 종료한다. 만약 target(탐색 대상)을 찾았다면 중간점의 인덱스를 반환하고 함수를 종료한다. 만약 target이 중간점의 원소보다 작다면 매개변수 end에 mid - 1을 대입하고 재귀함수를 호출한다. end에 mid - 1을 대입하는 이유는, target의 위치가 중간점의 인덱스보다 작으므로 중간점의 인덱스를 넘는 리스트의 원소들을 탐색할 필요가 없기 때문이다. target이 중간점의 원소보다 큰 경우에는 매개변수 start에 mid + 1을 대입한 후 재귀함수를 호출한다. 이유는 위와 비슷하다. target의 위치가 중간점의 인덱스보다 크므로 중간점의 인덱스보다 낮은 인덱스의 원소들을 탐색할 필요가 없기 때문이다.

result에 binary_search 함수의 return 값을 저장한다. result가 None이라면 결과는 존재하지 않으므로, 해당 값은 존재하지 않는다고 출력한다. 그렇지 않다면, result + 1의 순서에서 결과를 찾았다고 출력한다.

 

* 파이썬으로 구현한 Binary Search(반복문)

반복문으로 이진 탐색을 구현하였다. 재귀함수로 구현했을 때와 별 다른 것은 없다.

import sys

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

array = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
length = len(array)
target = int(sys.stdin.readline())

result = binary_search(array, target, 0, length - 1)

if result is None :
    print("결과가 존재하지 않습니다.")

else :
    print(f"{result + 1}번째 순서에서 결과를 찾았습니다.")