1. 분할정복(Divide-and-Conquer) 설계 전략

• 분할(Divide):

  해결이 쉬운 작은 부분문제로 분할

• 정복(Conquer):

  각 부분문제를 독립적으로 해결

• 통합(Combine):

  (필요하다면) 부분 해를 결합하여 전체 해를 구성

• 이 과정은 하향식(top-down) 접근법

2. 이분검색(Binary Search) — 분할정복적 구현

2.1 알고리즘 구조

• 문제:

  크기 n인 정렬된 배열 S에서 x의 위치를 찾음

• 전략:

  • 배열의 중간(mid) 원소와 x를 비교
  • 같으면 정답
  • x < S[mid]면 왼쪽, x > S[mid]면 오른쪽 부분배열에서 탐색(재귀)
  • 이 과정을 반복

• 재귀 구현 예시:

  cpp
  CopyEdit
  index location(index low, index high) {
      if (low > high) return 0;
      mid = (low + high) / 2;
      if (x == S[mid]) return mid;
      else if (x < S[mid]) return location(low, mid-1);
      else return location(mid+1, high);
  }
  
  

• 파라미터 최적화:

  S, x, n 등 변하지 않는 값은 전역 변수로 두고

  재귀에서는 index만 전달

• 꼬리 재귀(tail recursion):

  모든 재귀호출이 함수 마지막에서만 발생 → 반복문 변환이 용이

  반복 구현이 상수 배수만큼 빠르며 점근적 복잡도는 동일

2.2 최악 시간복잡도 분석

• 단위연산:

  x와 S[mid]의 비교

• **점화식 (n이 2의 거듭제곱):**W(n)=W(n/2)+1, W(1)=1

  W(n)=W(n/2)+1, W(1)=1W(n) = W(n/2) + 1,\ W(1) = 1

• **반복대입법:**W(n)=W(n/2)+1=W(n/4)+2=⋯=W(1)+log2n=1+log2n

  W(n)=W(n/2)+1=W(n/4)+2=⋯=W(1)+log⁡2n=1+log⁡2nW(n) = W(n/2) + 1 = W(n/4) + 2 = \dots = W(1) + \log_2 n = 1 + \log_2 n

• 수학적 귀납법 증명:

  1. 출발점: n=1 → W(1)=1=log₁+1
  2. 가정: W(n)=log₂n+1
  3. 단계: W(2n)=W(n)+1=log₂n+2=log₂2n+1

• **점근적 해:**W(n)=log2n+1 ∈ Θ(logn)

  W(n)=log⁡2n+1 ∈ Θ(log⁡n)W(n) = \log_2 n + 1\ \in\ \Theta(\log n)