Binary search

lastmod 2026-11-10created 2026-05-052 edits

Binary search(이진 탐색)는 정렬된 배열에서 중간 값과 비교해 탐색 범위를 절반씩 줄여 가며 원하는 값을 찾는 알고리즘이다. 시간 복잡도는 O(log n)으로 순차 탐색보다 훨씬 빠르지만 입력이 정렬되어 있어야 한다는 전제가 있다. 값의 존재 여부뿐 아니라 조건을 만족하는 경계(lower bound, upper bound)를 찾는 데도 응용되며, 표준 라이브러리의 bsearch, std::lower_bound, bisect 같은 함수가 이를 구현한다.