[알고리즘] 이진 탐색 (Binary Search)

이진 탐색이란?

이진 탐색(Binary Search)은 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘이다.

• 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
• 찾으려는 데이터와 중간점(Middle) 위치에 있는 데이터를 반복적으로 비교하여 탐색을 수행한다.

이진 탐색의 동작 방식

1. 배열의 가운데 값을 선택한다.
2. 찾고자 하는 값과 가운데 값을 비교한다.
3. 찾고자 하는 값이 가운데 값보다 크다면, 오른쪽 절반에서 탐색을 계속한다.
4. 찾고자 하는 값이 가운데 값보다 작다면, 왼쪽 절반에서 탐색을 계속한다.
5. 이를 반복하여 최종적으로 값을 찾거나, 범위가 사라질 때까지 진행한다.

이진 탐색의 시간 복잡도

이진 탐색은 한 번 비교할 때마다 탐색 범위가 절반으로 줄어든다. 따라서 최악의 경우에도 O(logN) 의 시간 복잡도를 가진다.

---

이진 탐색 구현 방법

이진 탐색을 구현하는 방법에는 크게 두 가지가 있다.

1. 재귀 함수(Recursive Function) 이용

def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    
    if array[mid] == target:
        return mid
    elif array[mid] < target:
        return binary_search(array, target, mid + 1, end)
    else:
        return binary_search(array, target, start, mid - 1)

# 입력 예시
n, target = map(int, input().split())
array = list(map(int, input().split()))

# 이진 탐색 실행
result = binary_search(array, target, 0, n - 1)
if result is None:
    print('원소가 존재하지 않습니다.')
else:
    print(result + 1)

2. 반복문(Iterative Method) 이용

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return None

# 입력 예시
n, target = map(int, input().split())
array = list(map(int, input().split()))

# 이진 탐색 실행
result = binary_search(array, target, 0, n - 1)
if result is None:
    print('원소가 존재하지 않습니다.')
else:
    print(result + 1)

---

빠른 입력을 위한 sys.stdin.readline()

위 코드에서 input()을 사용하면 실행 속도가 느려질 수 있다. 따라서, sys 라이브러리의 sys.stdin.readline()을 활용하면 시간 초과를 방지할 수 있다.

주의할 점

• sys.stdin.readline()으로 입력을 받을 경우, 입력 후 개행 문자(\n) 가 포함된다.
• 따라서 rstrip() 을 사용하여 개행 문자를 제거하는 것이 중요하다.

import sys

# 하나의 문자열 데이터 입력받기
input_data = sys.stdin.readline().rstrip()

---

파라메트릭 서치(Parametric Search)와 이진 탐색

파라메트릭 서치란?

파라메트릭 서치(Parametric Search)는 최적의 값을 찾기 위해 특정 조건을 만족하는 값의 범위를 탐색하는 방법이다.

• 최적화 문제를 결정 문제(Yes/No)로 바꾼 후 해결한다.
• 특정한 범위를 설정한 뒤, 이진 탐색을 이용하여 정답을 찾는 방식으로 풀이한다.

파라메트릭 서치와 이진 탐색의 관계

파라메트릭 서치는 이진 탐색을 응용한 문제 해결 방법이다.

• 일반적으로, 이진 탐색을 활용하여 범위를 좁혀가며 최적의 해를 찾는다.
• 예를 들어, 어떤 값이 가능한지 확인하는 함수(is_possible)를 설정하고, 이를 이용하여 이진 탐색을 수행한다.

예제 문제: 특정 조건을 만족하는 최대값 찾기

def is_possible(mid):
    # mid 값이 조건을 만족하는지 검사하는 함수 (문제에 따라 다름)
    return some_condition(mid)

def parametric_search(start, end):
    result = 0
    while start <= end:
        mid = (start + end) // 2
        if is_possible(mid):
            result = mid  # 가능한 값이면 저장하고 더 큰 값 탐색
            start = mid + 1
        else:
            end = mid - 1
    return result

파라메트릭 서치는 이진 탐색을 기반으로 하는 최적화 기법이므로, 이진 탐색을 잘 이해하면 쉽게 응용할 수 있다.