탐색 알고리즘(Search Algorithm)의 이진 탐색(Binary Search) 개념 정리

이진 탐색

탐색 알고리즘에는 크게 순차(Linear) 탐색과 이진 탐색(Binary Search)으로 구분된다. 순차 탐색은 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이고, 이진 탐색은 정렬되어 있는 리스트에서 시작점, 끝점, 중간점으로 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.

예시

이미 정렬된 10개의 데이터 중에서 이진 탐색을 통해 값이 4인 원소를 찾는 과정을 살펴보자.

[ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18 ]

탐색 과정

Step 1

시작점: arr[0], 끝점: arr[9], 중간점: arr[4] (소수점 이하 제거)

  *           *                  *
[ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18 ]

찾고자 하는 값(4)이 중간점의 값(8)보다 작으므로 중간점의 왼쪽으로 범위를 재설정한다.

[ 0, 2, 4, 6 ]

Step 2

시작점 : arr[0], 끝점: arr[3], 중간점: arr[1] (소수점 이하 제거)

  *  *     *
[ 0, 2, 4, 6 ]

찾고자 하는 값(4)이 중간점의 값(2)보다 크므로 중간점의 오른쪽으로 범위를 재설정한다.

[ 4, 6 ]

Step 3

시작점 : arr[0], 끝점: arr[1], 중간점: arr[0] (소수점 이하 제거)

  *  *
[ 4, 6 ]

찾고자 하는 값(4)이 중간점의 값(4)과 일치하므로 탐색을 종료한다.

전체 코드

단순 반복 방식

def iterativeBinarySearch(arr, value, start, end):
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == value:
            return mid

        elif arr[mid] < value:
            start = mid + 1

        else:
            end = mid - 1
    return None

nums = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
print(recursiveBinarySearch(nums, 4, 0, len(nums)-1))

재귀 함수 방식

def binarySearch(arr, value, start, end):
    if start > end:
        return None

    mid = (start + end) // 2

    if arr[mid] == value:
        return mid

    elif arr[mid] < value:
        return binarySearch(arr, value, mid + 1, end)

    else:
        return binarySearch(arr, value, start, mid - 1)


nums = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
print(binarySearch(nums, 4, 0, len(nums)-1))

이진 탐색의 시간 복잡도

위의 예시에서 보았듯이 탐색 범위를 2로 나누는 방식이다. 가령, 탐색하고자 하는 데이터의 개수가 32개이고, 최악의 상황을 고려하여 탐색해보면 그 과정은 다음과 같다.

• 1 단계 : 16개 가량의 데이터만 남는다.
• 2 단계 : 8개 가량의 데이터만 남는다.
• 3 단계 : 4개 가량의 데이터만 남는다.
• 4 단계 : 2개 가량의 데이터만 남는다.
• 5 단계 : 1개 가량의 데이터만 남고 탐색이 종료된다.

따라서, 시간 복잡도는 O(Log2N)이다.

최종 정리

생각하는 프로그래밍 저자인 존 벤틀리의 말에 따르면, 이진 탐색 코드를 제대로 작성한 프로그래머는 10% 내외라고 할 정도로 구현하기 까다롭다고 한다. 코딩 테스트에서 단골로 출제되는 문제인 만큼 여러 문제를 접하면서 다양한 코드를 익히도록 하되, 책에서는 가급적 외울 것을 권장하고 있다.