C와 C++의 이진 탐색
이 레슨에서는 C로 직접 작성한 반복문과 C++의 std::lower_bound로 정렬된 배열을 O(log n)에 탐색합니다.
소개
이진 탐색은 찾는 값과 탐색 구간 가운데 있는 요소를 비교한 다음, 그 값이 있을 수 없는 절반을 제외합니다. 이를 반복하면 구간이 아주 빠르게 줄어들지만, 입력 데이터는 반드시 정렬되어 있어야 합니다.
핵심 정리
- 빈 입력, 요소 하나, 중복 값, 이미 정렬된 데이터로 테스트하세요.
- 먼저 코드가 올바르게 동작하게 만든 다음 최적화하세요.
- 실제 코드에서는 표준 라이브러리의 이미 만들어진 함수를 우선 쓰세요.
C와 C++의 이진 탐색 시각화
O(log n)재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.
C와 C++ 코드 예제
C
main.c
#include <stdio.h>
int search(const int *values, int size, int target) {
int low = 0;
int high = size - 1;
while (low <= high) {
int middle = low + (high - low) / 2;
if (values[middle] == target) return middle;
if (values[middle] < target) low = middle + 1;
else high = middle - 1;
}
return -1;
}
int main(void) {
int values[] = {3, 7, 11, 16, 23, 28};
printf("index=%d\n", search(values, 6, 23));
}
index=4C++
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector values{3, 7, 11, 16, 23, 28};
auto match = std::lower_bound(values.begin(), values.end(), 23);
std::cout << "index="
<< std::distance(values.begin(), match) << '\n';
}
index=4C와 C++ 비교
C 버전에서는 인덱스가 아주 클 때 오버플로가 생기지 않도록 가운데 위치를 (low + high) / 2 대신 low + (high - low) / 2로 계산합니다. 비교할 때마다 low나 high가 남은 절반 쪽으로 움직입니다. C++ 버전은 std::lower_bound로 찾는 값보다 작지 않은 첫 위치를 찾습니다. 두 버전 모두 복잡도는 O(log n)입니다.
C
반복문, 포인터, 길이, 임시 버퍼를 모두 명시적으로 작성합니다.
C++
반복자와 표준 알고리즘이 처리 방식과 데이터를 저장하는 방식을 분리합니다.
연습 문제
두 버전을 모두 실행한 다음 코드를 바꿔 보면서 각 언어가 주는 안전성의 차이를 살펴보세요.
- 종이에 비교 과정을 하나씩 따라가 보세요.
- 중복 값과 아주 크거나 작은 값으로 테스트해 보세요.
- 직접 작성한 코드의 실행 시간을 재고 표준 라이브러리와 비교해 보세요.
챌린지로 연습하기
이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.
모든 챌린지