hello-algo/ko/docs/chapter_divide_and_conquer/binary_search_recur.md

분할 정복 탐색 전략

앞에서 배웠듯이 탐색 알고리즘은 크게 두 종류로 나뉜다.

• 완전 탐색: 자료 구조를 순회하며, 시간 복잡도는 $O(n)$이다.
• 적응형 탐색: 데이터 고유의 구성 방식이나 사전 정보를 이용하며, 시간 복잡도가 O(\log n) 또는 $O(1)$에 이를 수 있다.

실제로 시간 복잡도가 $O(\log n)$인 탐색 알고리즘은 보통 분할 정복 전략을 기반으로 구현된다. 이진 탐색과 트리가 그 예다.

• 이진 탐색은 각 단계에서 원래 문제(배열에서 목표 원소 찾기)를 더 작은 문제(배열의 절반에서 목표 원소 찾기)로 나눈다. 배열이 비거나 목표 원소를 찾을 때까지 계속한다.
• 트리는 분할 정복 사고의 대표적인 예다. 이진 탐색 트리, AVL 트리, 힙 등의 자료 구조에서 여러 연산의 시간 복잡도는 $O(\log n)$이다.

이진 탐색의 분할 정복 전략은 다음과 같다.

• 문제를 나눌 수 있다: 중간 원소와 목표 원소를 비교하여 원래 문제(배열에서 찾기)를 부분 문제(배열의 절반에서 찾기)로 재귀적으로 나눈다.
• 부분 문제가 독립적이다: 이진 탐색은 매번 부분 문제 하나만 처리하며 다른 부분 문제의 영향을 받지 않는다.
• 부분 문제의 해를 합칠 필요가 없다: 특정 원소 하나를 찾는 것이 목적이므로 부분 문제의 해를 합칠 필요가 없다. 부분 문제를 해결하면 원래 문제도 함께 해결된다.

분할 정복이 탐색 효율을 높이는 근본적인 이유는 완전 탐색이 매번 선택지 하나만 제외하는 데 비해 분할 정복 탐색은 매번 선택지의 절반을 제외할 수 있기 때문이다.

분할 정복으로 이진 탐색 구현

앞 장에서는 이진 탐색을 반복 방식으로 구현했다. 이제 분할 정복(재귀)으로 구현해 보자.

!!! question "문제"

길이가 $n$이고 모든 원소가 서로 다른 정렬된 배열 `nums`가 주어진다. 원소 `target`을 찾아라.

분할 정복의 관점에서 탐색 구간 $[i, j]$에 해당하는 부분 문제를 $f(i, j)$라고 하자.

원래 문제 $f(0, n-1)$에서 시작하여 다음 단계로 이진 탐색을 수행한다.

1. 탐색 구간 $[i, j]$의 중간 인덱스 $m$을 계산하고, 이를 기준으로 탐색 구간의 절반을 제외한다.
2. 크기가 절반으로 줄어든 부분 문제 f(i, m-1) 또는 $f(m+1, j)$를 재귀적으로 푼다.
3. target을 찾거나 구간이 빌 때까지 1. 단계와 2. 단계를 반복한 뒤 반환한다.

아래 그림은 배열에서 원소 $6$을 이진 탐색하는 분할 정복 과정을 보여 준다.

구현 코드에서는 문제 $f(i, j)$를 푸는 재귀 함수 dfs()를 정의한다.

[file]{binary_search_recur}-[class]{}-[func]{binary_search}