Python 코딩테스트 05: 이진 탐색

이진 탐색 (Binary Search) 이해와 응용

개요

이진 탐색(Binary Search)은 정렬된 배열이나 리스트에서 특정한 값을 효율적으로 찾는 알고리즘입니다.

이진 탐색은 배열을 반으로 나누어 탐색 범위를 좁혀가는 방식으로 작동하며, 시간 복잡도가 O(log n)으로 매우 빠릅니다.

이 포스팅에서는 이진 탐색의 원리, 구현 방법, 활용 예제 등을 자세히 설명하겠습니다.

 

이진 탐색의 원리

이진 탐색은 다음과 같은 단계로 진행됩니다:

1. 초기화: 배열의 중간 요소를 선택합니다.
2. 비교: 중간 요소와 찾고자 하는 값을 비교합니다.
   • 만약 중간 요소가 찾고자 하는 값이라면 탐색을 종료합니다.
   • 찾고자 하는 값이 중간 요소보다 작다면 배열의 왼쪽 절반을 탐색합니다.
   • 찾고자 하는 값이 중간 요소보다 크다면 배열의 오른쪽 절반을 탐색합니다.
3. 반복: 배열의 크기가 0이 될 때까지 1~2 단계를 반복합니다.

이 과정은 배열을 계속해서 반으로 나누기 때문에, 탐색 범위가 매우 빠르게 줄어듭니다.

 

이진 탐색의 단계별 예시

예시 배열

예를 들어, 정렬된 배열 [1, 3, 5, 7, 9, 11, 13]이 있다고 가정해봅시다. 여기서 숫자 7을 찾고자 합니다.

1. 초기화: 배열의 중간 요소인 7을 선택합니다.

   [1, 3, 5, 7, 9, 11, 13]
            ↑

2. 비교: 중간 요소 7이 찾고자 하는 값 7과 같습니다. 따라서 탐색을 종료합니다.

 

그림으로 보는 이진 탐색

Initial Array: [1, 3, 5, 7, 9, 11, 13]
Step 1: Choose middle element 7 (index 3)
Step 2: Compare 7 with target 7
Result: Found target at index 3

 

이진 탐색의 구현

이진 탐색은 재귀 방식과 반복 방식으로 구현할 수 있습니다.

반복 방식

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # target not found

# 예시 실행
arr = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(arr, target))  # 출력: 3

 

재귀 방식

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1  # target not found

    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

# 예시 실행
arr = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search_recursive(arr, target, 0, len(arr) - 1))  # 출력: 3

 

이진 탐색의 특징

• 시간 복잡도: O(log n)
• 공간 복잡도: O(1) (반복 방식), O(log n) (재귀 방식)
• 제약 조건: 배열이나 리스트가 정렬되어 있어야 함

 

이진 탐색의 활용

이진 탐색은 다음과 같은 다양한 문제에서 사용될 수 있습니다:

정렬된 리스트에서 값 찾기

정렬된 리스트에서 특정 값을 찾는 가장 효율적인 방법 중 하나가 이진 탐색입니다.

특정 범위 내의 값 찾기

이진 탐색을 응용하면 특정 범위 내의 값을 효율적으로 찾을 수 있습니다.

근사치 찾기

이진 탐색을 통해 특정 값에 가장 가까운 값을 찾는 문제도 해결할 수 있습니다.

 

응용 예제: 특정 값의 첫 번째와 마지막 인덱스 찾기

def find_first_and_last(arr, target):
    def find_position(is_first):
        left, right = 0, len(arr) - 1
        result = -1

        while left <= right:
            mid = (left + right) // 2
            if arr[mid] == target:
                result = mid
                if is_first:
                    right = mid - 1
                else:
                    left = mid + 1
            elif arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return result

    first = find_position(True)
    last = find_position(False)

    return (first, last)

# 예시 실행
arr = [1, 2, 2, 2, 3, 4, 5]
target = 2
print(find_first_and_last(arr, target))  # 출력: (1, 3)

 

그림으로 보는 이진 탐색 응용 예제

1. 초기 배열: [1, 2, 2, 2, 3, 4, 5]
2. 목표 값: 2
3. 첫 번째 인덱스 찾기:
   • 초기 left = 0, right = 6, mid = 3 (값: 2)
   • 값이 일치하므로 result 업데이트 후 right = mid - 1
   • 반복하여 left = 0, right = 2, mid = 1 (값: 2)
   • 값이 일치하므로 result 업데이트 후 right = mid - 1
   • 반복하여 left = 0, right = 0, mid = 0 (값: 1)
   • 값이 일치하지 않으므로 left = mid + 1
   • 반복 종료, 첫 번째 인덱스: 1
4. 마지막 인덱스 찾기:
   • 초기 left = 0, right = 6, mid = 3 (값: 2)
   • 값이 일치하므로 result 업데이트 후 left = mid + 1
   • 반복하여 left = 4, right = 6, mid = 5 (값: 4)
   • 값이 일치하지 않으므로 right = mid - 1
   • 반복하여 left = 4, right = 4, mid = 4 (값: 3)
   • 값이 일치하지 않으므로 right = mid - 1
   • 반복 종료, 마지막 인덱스: 3

 

결론

이진 탐색은 정렬된 배열이나 리스트에서 값을 효율적으로 찾는 강력한 알고리즘입니다.

시간 복잡도가 O(log n)으로 매우 효율적이며, 다양한 문제에 응용될 수 있습니다.

이진 탐색의 원리와 구현 방법을 이해하고, 다양한 문제에 적용해 보면서 그 활용 방법을 익히는 것이 중요합니다.

이를 통해 효율적이고 빠른 문제 해결이 가능해질 것입니다.