분할 정복 전략을 문제의 입력사례에 적용하여 문제를 풀 수 있음

= 문제의 입력 사례를 두 개 이상의 작은 입력 살례로 분할함

• 분할한 입력사례가 여전이 커서 답을 바로 구하지 못하면 그보다 더 작은 입력사례로 다시 분할함.
• 답을 구할 수 있을 때까지 입력사례를 계속 분할함

분할정복은 하향식 문제풀이 방식임

= 문제의 상위 입력사례의 해답은 하위의 작은 입력사례의 해답을 가지고 구한다는 의미

2.1 이분검색

이분검색의 절차

<aside> 💡

**x와 정 가운데 원소가 같으면 찾았으므로 종료함. 다르면,

1. [분할] 배열을 정 가운데 원소를 기준으로 반으로 분할함. x가 가운데 원소보다 작으면 왼쪽 배열을 선택. x가 가운데 원소보다 크면 오른쪽 배열을 선택

2. [정복] 선택한 반쪽 배열을 정복함. 즉, 선택한 반쪽 배열에 x가 있는지 재귀적으로 이분검색함.

3. [취합] 선택한 반쪽 배열에서 얻은 답이 최종 정답**

</aside>

→ 이분검색은 분할정복 알고리즘 중에서 가장 간단한 부류에 속함.

→ 입력사례를 분할하여 해답을 구하고, 결과를 취합하지 않아도 됨.

[예제 2.1]

x = 18이고 다음과 같은 배열이 있다고 가정

$$ 10 \ 12 \ 13\ 14\ 18\ 20\ "25"\ 27\ 30\ 35\ 40\ 45\ 47 $$

1. [분할] 배열을 분할함. x<25 이기 때문에 왼쪽 배열에서 검색함

10 12 13 14 18 20