이진 탐색

froajnzd·2024년 1월 20일

algorithm

목록 보기

7/11

Binary Search: 이진 탐색 / 이분 탐색
정렬된 데이터가 있을 때 중간부터 탐색을 시작하여 탐색할 문제를 점차 반씩 줄여가는 방식이다.

Binary Search의 특징
데이터가 정렬되어 있어야 한다.

시간복잡도
Best : $O(1)$
Average : $O(logN)$
Worst : $O(logN)$

📕 Binary Search를 사용해야하는 문제의 조건

원소가 정렬이 되어있어야 한다. (오름차순/내림차순 상관없음)
원소의 Random Access가 가능해야 한다.
: index만 알면 특정 arr[index]에 대해 $O(1)$ 의 시간복잡도로 참조할 수 있냐는 것 ➡ 그래야 이분탐색을 수행했을 때 $O(logN)$ 의 성능을 기대할 수 있음. 즉, 검색에 시간을 쓰면 안된다.
: 이런 관계로 linkedList에서는 이분탐색을 쓰지 않는다.

💡 Binary Search의 장점

검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다.

🥺 Binary Search의 단점

정렬된 리스트에만 사용할 수 있다.

📝 Binary Search를 사용하는 문제의 예

완전 탐색으로 풀면 시간 초과가 나는 경우 이진탐색을 통해 해결되는 경우가 많다.

탐색하고자 하는 데이터가 정렬되어 있어야 한다. 즉, 정렬되지 않은 데이터라면 먼저 정렬을 수행해야 한다.

문제에서 구하려고 하는 값의 범위를 고려하여 이진 탐색의 범위로 할당한다.

🎡 Binary Search를 응용하여 푸는 다른 알고리즘

Parametric Search (파라메트릭 서치)
: 이분탐색과 매우 유사하게 L,R을 두고 Mid에 대한 판별을 이용한다. 결국 $O(logN)$ 의 시간복잡도를 갖는다.
: 이분탐색과의 가장 큰 차이는, 최적화 문제를 결정 문제로 바꾸어 푸는 것이라는 거다.

🎁 구현 방법

구현은 두 가지 방법으로 할 수 있다.
1. 재귀(recursion)
2. 반복(iteration)
: 함수 프롤로그와 에필로그의 오버헤드를 줄일 수 있는 반복(iteration) 방식으로 구현하는 것이 성능이 일반적으로 더 좋고 간편하다.

동작 방식

배열의 중간 값을 가져온다
중간 값과 검색 값을 비교한다.
a. 중간 값이 검색 값과 같다면 종료한다
b. 중간 값보다 검색 값이 크다면 중간값 기준, 배열의 오른쪽 구간을 대상으로 탐색을 반복한다
c. 중간 값보다 검색 값이 작다면 중간값 기준, 배열의 왼쪽 구간을 대상으로 탐색을 반복한다

종료 조건
두 가지 중 한 가지를 만족한다면 탐색을 종료한다.

검색을 성공한 경우
: array[mid] == key
검색을 실패한 경우
: low >= high

🏃‍ 예시 문제 1

<BAEKJOON: 실버 2> 예산

해답

import sys
input = sys.stdin.readline

N = int(input())
city = list(map(int, input().split()))
total_budget = int(input())

start, end = 0, max(city)
mid = (start + end) // 2

while start <= end:
    # 상한가가 mid일 때 사용될 예산 총 값 구하기
    use_budget = 0
    for i in range(N):
        if mid < city[i]:
            use_budget += mid
        else:
            use_budget += city[i]
    # binary search
    if use_budget == total_budget:
        break
    elif use_budget > total_budget:
        end = mid - 1
        mid = (start + end) // 2
    else:
        start = mid + 1
        mid = (start + end) // 2

print(mid)