[크래프톤 정글 ] 이분 탐색

이분 탐색(Binary Search)은 정렬된 배열이나 정렬된 순서가 보장된 데이터 구조에서 특정 값을 효율적으로 찾는 알고리즘이다. 이 알고리즘은 탐색 범위를 절반으로 줄이면서 진행하므로, 시간 복잡도가 (O(\log n))으로 매우 효율적이다. 이제 이분 탐색의 핵심 개념과 주요 특징을 깊이 있게 정리해 보겠다.

1. 기본 개념

이분 탐색은 탐색 범위를 절반으로 계속 줄여가며 목표 값을 찾는 방식으로 동작한다. 예를 들어, 배열이 오름차순으로 정렬되어 있다고 가정했을 때, 이분 탐색은 다음과 같은 과정을 따른다:

1. 초기 설정:

   • st (시작 인덱스)를 배열의 첫 번째 인덱스인 0으로 설정.
   • en (끝 인덱스)를 배열의 마지막 인덱스로 설정.

2. 반복적인 비교:

   • 중간값 인덱스 mid를 계산: mid = (st + en) / 2.
   • arr[mid]와 찾고자 하는 값 target을 비교:
     • arr[mid] == target이면 값을 찾았으므로 해당 인덱스를 반환.
     • arr[mid] < target이면 찾고자 하는 값은 오른쪽 절반에 있으므로, st = mid + 1로 업데이트.
     • arr[mid] > target이면 찾고자 하는 값은 왼쪽 절반에 있으므로, en = mid - 1로 업데이트.

3. 종료 조건:

   • st가 en보다 커지면, 탐색 범위가 없으므로 찾고자 하는 값이 배열에 없음을 의미. 이 경우 탐색을 종료하고 실패를 반환.

2. 이분 탐색의 특징

• 정렬 필요: 이분 탐색이 제대로 동작하려면 배열이 반드시 정렬되어 있어야 한다.
• 시간 복잡도: (O(log n))으로, 크기가 (n)인 배열에서 최대 (log_2 n)번의 비교로 목표 값을 찾을 수 있다.
• 공간 복잡도: 기본적인 이분 탐색은 (O(1))의 추가 공간을 사용한다. (재귀적으로 구현할 경우, 호출 스택 때문에 (O(log n))의 공간 복잡도를 가질 수 있다.)

3. 다양한 응용

이분 탐색은 단순히 배열에서 값을 찾는 것 외에도 여러 문제에 응용될 수 있다. 예를 들어:

• Lower Bound: 배열에서 특정 값 이상이 처음으로 나타나는 위치를 찾기 위해 이분 탐색을 사용.
• Upper Bound: 배열에서 특정 값보다 큰 값이 처음으로 나타나는 위치를 찾기 위해 이분 탐색을 사용.
• 매개변수 탐색 (Parametric Search): 최적화 문제를 풀기 위해 이분 탐색을 사용. 예를 들어, 특정 조건을 만족하는 가장 작은 값이나 가장 큰 값을 찾을 때.

4. 구현 시 주의할 점

• 중간값 계산의 오버플로: (st + en) / 2로 중간값을 계산할 때, 큰 인덱스 값이 더해지면 정수 오버플로가 발생할 수 있다. 이를 방지하기 위해 (st + (en - st) / 2)로 중간값을 계산하는 것이 좋다.
• 종료 조건: 탐색 범위가 적절히 줄어들지 않으면 무한 루프에 빠질 수 있다. st와 en의 업데이트가 정확한지 항상 확인해야 한다.

5. 이분 탐색의 변형 및 확장

• 무한 배열 이분 탐색: 끝이 없는 배열에서 값을 찾는 이분 탐색의 변형. 일반적인 방법은 먼저 범위를 찾아내는 작업을 선행한 후, 그 범위 내에서 이분 탐색을 수행하는 것이다.
• 이분 탐색 트리 (Binary Search Tree): 이분 탐색의 개념이 확장되어 데이터 구조로 발전한 형태. 트리 형태로 데이터가 구성되어 있으며, 노드 간의 관계가 정렬된 상태로 유지되므로 탐색에 (O(log n)) 시간이 걸린다.

6. 예제

간단한 이분 탐색의 논리를 따라가 보자:

1. 주어진 배열이 [1, 3, 5, 7, 9]이고, 찾고자 하는 값이 7이라고 가정.
2. st = 0, en = 4로 설정.
3. mid = (0 + 4) / 2 = 2. arr[mid] = 5. (찾고자 하는 값보다 작음)
4. 따라서, st = mid + 1 = 3으로 업데이트.
5. 이제 새로운 mid = (3 + 4) / 2 = 3. arr[mid] = 7.
6. 찾고자 하는 값과 일치하므로 3을 반환. (값을 찾음)

7. 구현

def binary_search(arr, target):
    st = 0
    en = len(arr) - 1

    while st <= en:
        mid = st + (en - st) // 2  # 중간값 계산, 오버플로 방지를 위해 사용

        if arr[mid] == target:
            return mid  # 찾는 값을 발견하면 인덱스를 반환
        elif arr[mid] < target:
            st = mid + 1  # 찾는 값이 더 크다면 오른쪽 절반을 탐색
        else:
            en = mid - 1  # 찾는 값이 더 작다면 왼쪽 절반을 탐색

    return -1  # 찾는 값이 배열에 없으면 -1을 반환