분할 정복 알고리즘 중 이진 탐색의 특성 및 코드 구현

목차

1. 문제
2. 선택한 알고리즘
3. 알고리즘의 특성
4. 알고리즘의 동작원리 및 성능
5. 알고리즘의 시간 복잡도
6. 알고리즘 코드 및 시간 복잡도

본문내용

문제
본 알고리즘과목에서 설명한 여러 알고리즘 중 하나를 선정하여 알고리즘의 특성, 동작 원리 및 복잡도를 설명하시오. (추가 개선 사항을 제시한다면 가점 부여)

선택한 알고리즘
분할 정복 알고리즘 중 이진 탐색(Binary Search)알고리즘을 선택하였다.
이진 탐색이란, 정렬된 자료를 반으로 계속해서 나누어 탐색하는 방법이다. 아래와 같이 자료를 계속해서 반으로 쪼개서 찾고자 하는 자료를 찾는 것이다.

알고리즘의 특성
1. 정렬된 데이터에 대한 효과적인 탐색 방법이다. (오름차순으로 정렬되었다고 가정)
2. 입력이 정렬된 리스트에 대해서만 적용 가능하다.
- 정렬이 되어있지 않은 경우 찾고자 하는 데이터를 지나치는 경우가 빈번하게 발생해 자료가 있음에도 불구하고 찾지 못하게 될 수 있다.
3. 삽입/삭제 연산 시 데이터의 정렬 상태 유지가 필요하다.
4. 평균적으로 n/2개의 데이터 이동이 발생한다.
5. 삽입/삭제가 빈번한 응용에 부적합하다.

참고 자료

없음