[Do it! 알고리즘 코딩 테스트 자바] 이진 탐색 (12일차)

이진 탐색 (Binary Search)

• 정의: 정렬된 데이터 배열에서 탐색 범위를 절반씩 분할하며 원하는 타겟 값의 위치를 찾는 고속 탐색 알고리즘.
• 핵심 원리:
  • 정렬 전제 조건: 탐색 수행 전 배열의 데이터가 반드시 오름차순이나 내림차순으로 정렬되어 있어야 함.
  • 포인터 활용 (분할 정복): 탐색 범위의 시작점(start), 끝점(end), 중간점(mid) 3개의 변수(포인터)를 설정하여 범위를 조작.
  • 범위 축소 방식: 타겟 값이 중간점(mid) 값보다 작으면 왼쪽 절반을 탐색(end = mid - 1), 크면 오른쪽 절반을 탐색(start = mid + 1)하는 과정을 반복.
  • 시간 복잡도 최적화: 매 비교마다 탐색 공간이 반으로 줄어들므로 시간 복잡도는 O(log N)을 보장. 데이터 규모가 커질수록 선형 탐색(O(N)) 대비 압도적인 효율 발휘.
  • 종료 조건: 중간점 데이터가 타겟 값과 일치하여 탐색에 성공하거나, 시작점이 끝점보다 커져서(start > end) 더 이상 탐색할 범위가 없을 때 탐색 종료.