이진 탐색
이진 탐색 (Binary Search)
이진 탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾는 효율적인 탐색 알고리즘입니다. 탐색 범위를 반복적으로 절반씩 줄여나가며 원하는 값을 찾기 때문에, O(log n)의 매우 빠른 시간 복잡도를 가집니다.
🔍 이진 탐색의 동작 원리
이진 탐색은 반드시 데이터가 정렬되어 있어야 한다는 전제 조건이 있습니다.
1. 배열의 시작(low), 중간(mid), 끝(high) 인덱스를 설정합니다. 2. 중간(mid) 위치의 원소와 찾고자 하는 값(target)을 비교합니다. 3. 만약 중간 원소가 target과 같다면, 탐색을 종료합니다. 4. 만약 target이 중간 원소보다 작다면, 탐색 범위를 왼쪽 부분 배열(low ~ mid-1)로 좁힙니다. 5. 만약 target이 중간 원소보다 크다면, 탐색 범위를 오른쪽 부분 배열(mid+1 ~ high)로 좁힙니다. 6. 탐색 범위가 없어질 때까지(low > high) 2~5번 과정을 반복합니다.
- 구현 방법 : `while` 루프를 사용하는 반복문 방식과, 함수가 자기 자신을 호출하는 재귀 방식으로 모두 구현할 수 있습니다.
👍 이진 탐색의 장점과 단점
- 장점 (Advantages)
> * 매우 빠른 탐색 속도 : 탐색을 거듭할수록 검색 범위가 절반으로 줄어들기 때문에, O(log n)의 매우 빠른 시간 복잡도를 가집니다.
- 단점 (Disadvantages)
> * 정렬 필수 : 반드시 데이터가 정렬되어 있어야 한다는 전제 조건이 있습니다. (정렬되지 않은 데이터라면, 정렬 비용(e.g., O(n log n))이 추가로 발생) > * 데이터 변경에 비효율적 : 배열 기반이므로, 데이터의 삽입/삭제가 빈번한 경우 배열의 구조를 유지하는 데 비용이 많이 들어 비효율적입니다.
💡 개발자 핵심 Point
- 이진 탐색은 단순히 '정렬된 배열에서 값 찾기'를 넘어, '최적의 해 찾기' 문제로 확장될 수 있습니다.
- 파라메트릭 서치 (Parametric Search)
> * '개념': 최적화 문제(e.g., 특정 조건을 만족하는 최솟값/최댓값 찾기)를 '결정 문제'(Yes/No로 답할 수 있는 문제)로 바꾸어, 이진 탐색을 통해 해결하는 기법입니다. > * '예시': "나무를 잘라 최소 M미터의 나무를 얻기 위한 절단기의 최대 높이는?" → "절단기 높이가 H일 때, M미터 이상의 나무를 얻을 수 있는가? (Yes/No)" 문제로 바꾸어, H의 범위를 이진 탐색으로 좁혀가며 최적의 H를 찾습니다.
- Lower Bound & Upper Bound
> * Lower Bound : 정렬된 배열에서 찾고자 하는 값(target) 이상의 값이 처음으로 나타나는 위치입니다. > * Upper Bound : 정렬된 배열에서 찾고자 하는 값(target)을 초과하는 값이 처음으로 나타나는 위치입니다. > * 이 두 가지를 활용하면, 정렬된 배열에서 특정 값의 개수를 효율적으로 찾을 수 있습니다 (`Upper Bound - Lower Bound`).
- 많은 언어의 표준 라이브러리에서 이진 탐색 관련 함수를 제공합니다. (e.g., Java의 `Arrays.binarySearch()`, C++의 `binary_search`, `lower_bound`, `upper_bound`)
