[알고리즘] 분할정복 - 이진검색

💡 분할정복(Divide-and-Conquer)

   - 해결하기 쉽도록 문제를 여러개의 작은 부분으로 나누고 나눈 문제를 각각 해결하는 방식(하양식 방식, top-down)

 

 

💡 이진검색 

 - 찾고자 하는 원소 x 와 정렬된 배열에서 배열의 중간에 위치한 항목과 일치한지 비교

 - 일치하지 않을 경우, x가 중앙보다 작으면 왼쪽, 크면 오른쪽 반쪽을 선택해 다시 해당 반쪽의 중앙을 선택

    (반쪽 배열에서 재귀적으로 이분 검색)

 

//이진검색 알고리즘

 

✔ 최악의 경우 시간복잡도 분석

- n이 2의 제곱일 때와 아닐때로 나눌 수 있지만 자세한 설명은 생략하고

   W(n) = ⌊logn⌋ +1  *n이 크면 1은 무시

- 귀납적 증명