1. 분할정복 - 이진탐색

분할정복

           > 1. 주어진 문제의 입력을 나눌수 없을 때까지 두개이상 작은 문제로 순환적으로 분할

              2. 작은 문제들을 각각 해결

              3. 그해를 결합하여 원래 문제의 해를 구하는 방식

분할 > 정복  > 결합

이진탐색 : n개 -> n/2 + (n/2) 분할 -> (n/4) + n/4 + (n/4 + n/4) 분할한 것의 일부만 사용

합병정렬 : n개 -> n/2 + n/2 분할 -> n/4 + n/4 + n/4 + n/4

퀵정렬 :   n개 -> a + b 분할 ->c+d+e+f

선택문제: n개 ->  a + (b) 분할 ->(c)+d+(e+f) 분할한 것의 일부만 사용

---

이진탐색

> 정렬된 상태의 데이터에 대해 적용 

분할 : 가운데 원소를 기준으로 왼쪽과 오른쪽 부분배열로 분할, 탐색키와 가운데 원소가 같으면 해당 원소의 배열 인덳를 반환/종료

정복 : 탐색 키 X가 가운데 원소보다 작으면 왼쪽 부분배열 대상으로 이진 탐색을 순환 호출, 크면 오른쪽 부분배열을 대상으로 이진탐색 순환 호출

결합 : 부분배열에 대한 탐색 결과가 직접 반환되므로 결합이 불필요

-순환형태-

BinarySearch(A[] , Left, Right, x)

{

    if(Left > Right)return -1;//탐색 실패

   Mid = (Left+Right/2);

   if(x == A[Mid]) return Mid;

   else if(x < Mid)Binary Search(A, Left, Mid-1, x) //왼쪽 부분배열

   else BinarySearch(A, Mid+1, Right, x)//오른쪽 부분배열

}

-반복형태- >> 효율이 좋음

BinarySearch(A[] ,n, x)

{

    Left = 0; Right = n-1;

    while (Left <=Right){

        Mid ==(Left + Right)/2;

        if(x==A[Mid]) return Mid;

         else if (x<Mid) Right = Mid -1; //왼쪽 부분배열

         else Left = Mid +1;//오른쪽 부분배열

   }

    return -1;

}

n/2^k =1

k = logn  ==> 데이터 8 개 면 3번 분할. 

> 최대 비교횟수 = 최대 분할 횟수 +1  ==>4번 분할. 

성능

T(n) : 입력 크기 n에 대한 탐색 가정에서의 모든 비교횟수의 합. 

     = 맨 바깥 수준에서의 비교횟수 + 순환 호출에서의 비교횟수. 

-점화식-

T(n) = T(n/2) +O(1)(n>1), T(1) =1

T(n) = logn

>입력이 정렬된 리스트에 대해서만 적용가능

> 삽입/삭제 연산 시 데이터 정렬 상태 유지가 필요

    - 평균 n/2개의 데이터 이동이 발생 -> 삽입/삭제가 빈번한 응용에는 부적합.