이진 검색

1. 문제 제시 : 병뚜껑 속의 숫자 게임

---

2. 이진 검색(Binary Search)

• 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법입니다.
  • 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행합니다.
• 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 합니다.

---

3. 분할 정복의 활용

• 병합 정렬은 외부 정렬의 기본이 되는 정렬 알고리즘입니다. 또한, 멀티코어(Multi-Core) CPU나 다수의 프로세서에서 정렬 알고리즘을 병렬화하기 위해 병합 정렬 알고리즘이 활용됩니다.
• 퀵 정렬은 매우 큰 입력 데이터에 대해서 좋은 성능을 보이는 알고리즘입니다.

---

4. 연습 문제