[알고리즘] 이진 탐색

이진 탐색

리스트 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 탐색 알고리즘이다. 이미 데이터가 정렬되어 있다면 매우 빠르게 타겟값을 찾을 수 있다.

이진 탐색은 위치를 나타내는 변수를 3개를 사용한다. 리스트의 시작점, 끝점, 그리고 중간점이다. 타겟값과 중간점에 있는 데이터를 반복적으로 비교하며 타겟값을 찾는다.

예시

숫자 1, 3, 5, 7, 9, 11, 13, 15, 17, 19가 순서대로 저장되어 있을 때 15를 찾는 과정을 알아보자.

준비된 데이터

시작점을 리스트의 맨 처음 인덱스([0]), 끝점을 리스트의 맨 뒤 인덱스([9])로 설정한다. 중간점은 0과 9의 중간값인 [4]번 인덱스가 된다.(소수점 이하는 버린다.)

찾고자 하는 값인 15가 중간점의 데이터 값의 9보다 크므로 중간값 이전의 값은 확인할 필요가 없다.

시작점은 중간점 다음인 [5]번 인덱스이고 끝점은 그대로 [9]번 인덱스이다. 중간점은 5와 9의 중간값인 [7]번 인덱스가 된다.

중간점의 데이터 15는 찾고자 하는 값인 15와 일치하므로 탐색을 종료한다.

코드

1. 재귀 함수로 구현한 이진 탐색 코드

def binary_search_function(target, start, end, array):
    ## 타겟값을 찾지 못했을 때
    if start > end:
        return None
    mid = (start+end) // 2 
    ## 타겟값을 찾았을 때
    if array[mid] == target:
        return mid
    ## 타겟값보다 중간값이 더 클 때
    elif array[mid] > target:
        ## 왼쪽 확인
        binary_search_function(target, start, mid-1, array)
    ## 타겟값이 중간보다 클 때
    else:
        ## 오른쪽 확인
        binary_search_function(target, mid+1, end, array)

2. 반복문으로 구현한 이진 탐색 코드

def binary_search_iteration(target, start, end, array):
    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

시간 복잡도

이진 탐색은 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다. 따라서 $O(logN)$의 시간 복잡도를 가진다.

한 번 확인할 때마다 데이터가 절반씩 줄어든다는 점은 퀵 정렬과 공통점이 있다.

정리

1. 이진 탐색은 시작점, 끝점, 그리고 중간점을 사용해서 탐색한다.

2. 타겟값과 중간점의 데이터를 반복적으로 비교하며 타겟값을 탐색한다.

3. 재귀 함수와 반복문을 사용해서 구현할 수 있다.

4. 데이터의 개수가 N개일 때 O(logN)의 시간 복잡도를 갖는다.