탐색 알고리즘 - 이진 탐색

1.  이진 탐색

이진 탐색은 탐색의 범위를 절반씩 좁혀가며 데이터를 탐색하는 알고리즘입니다. 

이진탐색 알고리즘은 리스트 내 데이터가 어느 정도 정렬되어 있어야만 사용 가능하며 데이터가 무작위로 정렬되어 있다면 사용할 수 없습니다. 

이진 탐색 알고리즘은 입력 데이터가 많거나(e.g., 1,000만 개 이상) 탐색 범위의 크기가 매우 넓을 때(e.g., 1,000억 이상) 효과적으로 문제를 해결할 수 있습니다.

2.  이진 탐색의 동작 과정

이진 탐색은 특정 데이터를 찾기 위해 리스트 내 기준점으로서 시작 인덱스, 중간 인덱스, 마지막 인덱스를 사용합니다.

 

이진 탐색의 동작 순서는 아래와 같습니다.

 

1️⃣ 시작 인덱스와 마지막 인덱스 사이의 중간 값에서 소수점 이하를 버려 중간 인덱스를 정합니다.

2️⃣ 중간 인덱스에 해당하는 데이터와 현재 찾으려는 데이터가 같은지 비교합니다.

3️⃣ 중간 값이 더 크면 중간 인덱스 이후의 값은 확인하지 않고, 마지막 인덱스를 중간 인덱스로부터 한 칸 앞으로 옮깁니다.

반대로, 중간 값이 더 작다면 시작 인덱스를 중간 인덱스로부터 한 칸 뒤로 옮깁니다.

4️⃣ 중간 인덱스의 값과 찾으려는 값이 같아질 때까지 2️⃣ 과정과 3️⃣ 과정을 반복합니다.

 

이제 구체적인 예시를 통해 동작 과정을 알아보겠습니다. 아래와 같이 리스트 내 10개의 데이터 중에서 값이 4인 원소를 이진 탐색을 통해 찾아보겠습니다.

 

편의상 찾고자 하는 데이터(target data)는 파란색으로 표현하고, 탐색할 필요가 없는 데이터는 회색으로 채우겠습니다.

 

(1) 리스트 내 원소가 총 10개이므로 시작 인덱스는 [0]이고 마지막 인덱스는 [9]입니다. 중간 인덱스는 시작 인덱스와 마지막 인덱스의 중간 지점인 [4]가 됩니다. [4.5]에서 소수점 이하를 버리기 때문이죠.

 

 

(2) 중간 인덱스의 값인 8은 찾으려는 값 4보다 크기 때문에, 중간 인덱스 이후의 값은 이제 따로 탐색하지 않습니다. 이제 마지막 인덱스를 중간 인덱스 한 칸 앞으로 옮깁니다. 즉, 기존 중간 인덱스가 [4]였기 때문에 마지막 인덱스는 [3]이 됩니다. 중간 인덱스는 [0]과 [3] 중간 값인 [1]이 됩니다(실제 중간 값인 [1.5]에서 소수점 이하를 제거하였습니다).

 

 

(3) 중간 인덱스의 값인 2는 찾으려는 데이터 4보다 작기 때문에 2 이하의 데이터는 탐색할 필요가 없습니다. 따라서 시작 인덱스를 중간 인덱스의 한 칸 뒤인 [2]로 옮깁니다. 이제 새로운 중간 인덱스는 [2]와 [3] 사이의 [2]가 됩니다([2.5]에서 소수점 이하 절사). 중간 인덱스에 위치한 데이터 4는 찾으려는 데이터 4와 같기 때문에 이 시점에서 탐색을 종료합니다.

 

3.  이진 탐색의 구현(Python)

파이썬 기반에서 이진 탐색은 2가지 방법으로 구현이 가능합니다. 첫 번째는 재귀 함수를 사용하는 것이고, 다른 한 가지 방법은 반복문을 이용하는 것입니다. 각 방법별로 구현 방법을 알아보도록 하겠습니다.

3.1.  재귀 함수를 활용한 구현

# 재귀함수를 활용한 이진 탐색 구현
def binary_search (arr, target, start, end):
    
    if start > end:
        return None
    
    # 중간 인덱스는 시작 인덱스와 마지막 인덱스 사이의 중간 인덱스
    # 몫만 구하기 위해 // 연산자 활용
    mid = (start + end) // 2
    
    # 중간 인덱스의 값이 타겟 데이터와 같은 경우 탐색 종료
    if arr[mid] == target:
        return mid
        
    # 중간 인덱스의 값이 타겟 데이터보다 큰 경우
    # 마지막 인덱스를 중간 인덱스의 한 칸 앞으로 이동
    elif arr[mid] > target:
        return binary_search(arr, target, start, mid-1)
        
    # 중간 인덱스의 값이 타겟 데이터보다 작은 경우
    # 시작 인덱스를 중간 인덱스의 한 칸 뒤로 이동
    else:
        return binary_search(arr, target, mid+1, end)

arr = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
n = len(arr)
# 찾으려는 값으로서 임의로 4로 설정
target = 4

# 시작 인덱스 및 마지막 인덱스를 전달인자로 할당
res = binary_search(arr, target, 0, n-1)
print("{}번째에서 타겟 확인.".format(res + 1))

 

3.2.  반복문을 활용한 구현

# 반복문을 활용한 이진 탐색 구현
def binary_search (arr, target, start, end):
    while start <= end:
        # 중간 인덱스는 시작 인덱스와 마지막 인덱스 사이의 중간 인덱스
        # 몫만 구하기 위해 // 연산자 활용
        mid = (start + end) // 2
    
        # 중간 인덱스의 값이 타겟 데이터와 같은 경우 탐색 종료
        if arr[mid] == target:
            return mid
        
        # 중간 인덱스의 값이 타겟 데이터보다 큰 경우
        # 마지막 인덱스를 중간 인덱스의 한 칸 앞으로 이동
        elif arr[mid] > target:
            end = mid - 1
        
        # 중간 인덱스의 값이 타겟 데이터보다 작은 경우
        # 시작 인덱스를 중간 인덱스의 한 칸 뒤로 이동
        else:
            start = mid + 1
            
    return None

arr = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
n = len(arr)
# 찾으려는 값으로서 임의로 4로 설정
target = 4

# 시작 인덱스 및 마지막 인덱스를 전달인자로 할당
res = binary_search(arr, target, 0, n-1)
print("{}번째에서 타겟 확인.".format(res + 1))

4.  이진 탐색의 시간 복잡도

앞서 살펴본 예시에서는 리스트 내 데이터가 총 10개였지만, 이진 탐색을 이용하면 총 3회의 탐색을 통해 원하는 데이터를 찾을 수 있었습니다. 이진 탐색은 탐색 횟수별로 확인하는 데이터의 개수가 절반씩 줄어들기 때문에 시간 복잡도가 O(log N) 입니다. 이처럼 확인하는 데이터의 개수가 절반씩 줄어드는 특징은 퀵 정렬과 동일합니다.

그렇다면 이진 탐색은 언제 사용하면 좋을까요?

탐색해야 하는 데이터의 개수나 값이 1,000만 단위 이상일 경우 이진 탐색과 같이 시간 복잡도가 O(log N) 수준으로 빠른 속도를 낼 수 있는 알고리즘을 활용하는 것이 좋습니다.