이진 탐색(Binary Search)의 동작 원리와 시간 복잡도를 설명해주세요.

이진 탐색은 정렬된 배열에서 특정 값을 효율적으로 찾는 알고리즘입니다. 작동 원리는 다음과 같습니다. 먼저 배열의 중간값을 확인하고, 찾고자 하는 값이 중간값보다 작으면 배열의 왼쪽 절반을, 크면 오른쪽 절반을 탐색 범위로 좁힙니다. 이 과정을 찾을 때까지 반복합니다.

핵심은 탐색 범위를 절반씩 줄여나간다는 점입니다. 따라서 시간 복잡도는 O(log N)입니다. 예를 들어 16개의 요소가 있는 배열에서 최악의 경우에도 4번 안에 값을 찾을 수 있습니다. 분할 정복 알고리즘의 대표적인 예시라고 할 수 있습니다.