1. 이진 검색이 필요한 이유
프로그래밍을 처음 배울 때는 검색이 항상 «루프를 돌며 비교한다»인 것처럼 보입니다. 그리고 사실입니다… 데이터가 적고 시간이 넉넉할 때까지는요. 하지만 수천 개의 요소가 있고(예: 사용자 동작마다 검색을 해야 하는 경우) 검색이 여러 번 실행되면 선형 검색은 성가시게 느껴집니다 — 마치 노트북에서 “Release + LTO” 모드로 프로젝트를 컴파일할 때 한 줄만 확인하고 싶었던 상황과 비슷합니다.
이진 검색은 정렬된 데이터에서 로그 시간에 검색하는 방법입니다. 직관적으로 말하면: 요소를 하나씩 검사하는 대신 매번 범위의 절반을 “버립니다”. 정렬된 배열에서는 중앙만 보면 다음에 어디를 찾아야 할지 알 수 있으므로 이 방법이 완벽하게 동작합니다.
중요: STL에서 이진 검색은 하나의 함수가 아니라 알고리즘의 가족입니다. 목적이 서로 다릅니다:
- std::binary_search는 «그런 요소가 존재하는가?»에 답합니다.
- std::lower_bound는 «요소가 있어야 할 위치는 어디인가(그가 나타날 수 있는 첫 번째 위치)?»에 답합니다.
- std::upper_bound는 «이 키와 동등한 모든 요소는 어디서 끝나는가?»에 답합니다.
오늘은 결과를 올바르게 해석하는 방법을 배웁니다 — 추측이나 샤먼식 방법 없이요.
2. 전제 조건: 같은 순서로 정렬되어야 함
이진 검색은 매우 정직한 알고리즘입니다: 자신이 세상을 이해하는 척하지 않습니다. 한 가지를 믿습니다 — 범위가 이미 정렬되어 있다는 것. 그리고 그것은 «대충»이나 «어느 정도»가 아니라 검색에 사용되는 규칙과 정확히 같은 규칙이어야 합니다. 만약 나이를 기준으로 정렬해놓고 이름으로 검색한다면 — 그건 다른 순서이며, 이진 검색은 거의 무작위 답을 생성하는 기계가 됩니다(시험 답을 외우지 않은 학생이 문제를 대충 답하는 것과 비슷합니다).
이것을 오늘의 만트라로 고정합시다:
정렬과 이진 검색은 동일한 순서(같은 operator< 또는 같은 비교자)를 사용해야 합니다.
이진 검색이 «보기를 기대하는» 것을 시각화하면:
flowchart TD
A[요소들의 범위가 있다] --> B{정렬되어 있는가?}
B -- 아니오 --> C[이진 검색은 의미가 없음: 답이 틀릴 수 있음]
B -- 예 --> D{정렬 규칙 = 검색 규칙인가?}
D -- 아니오 --> C
D -- 예 --> E[binary_search / lower_bound / upper_bound 적용 가능]
실무에서 이는 간단한 규율을 의미합니다: 비교자 comp가 있다면 같은 comp를 std::sort, std::lower_bound, std::upper_bound에 모두 사용하세요. «비슷한», «거의 같은» 것이 아니라 문자 그대로 같은 것을 사용해야 합니다.
3. STL의 검색 알고리즘
std::binary_search: 존재 여부에 대한 응답
std::binary_search(first, last, value)는 bool을 반환합니다. 위치나 개수, 또는 인생의 부조리에 대한 설명은 알려주지 않습니다. 단지 말합니다: «이 정렬된 범위에서 이 순서에 따라 value와 동등한 요소가 존재하는가».
숫자로 간단한 예제부터 시작합시다 — 메커니즘을 보기 더 쉽습니다.
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{1, 2, 4, 4, 7};
std::cout << std::binary_search(v.begin(), v.end(), 4) << "\n"; // 1
std::cout << std::binary_search(v.begin(), v.end(), 5) << "\n"; // 0
}
여기서 중요한 것은 v가 이미 정렬되어 있다는 점입니다. 예를 들어 std::vector<int> v{4, 1, 7, 2, 4};처럼 되어 있으면 binary_search가 올바르게 동작한다는 보장이 없습니다: 정렬되지 않은 순서를 절반으로 나누기 때문에 잘못된 결론을 내릴 수 있습니다.
binary_search가 유용한 경우는? 단지 «그 키가 있는가»만 빠르게 답해야 할 때입니다. 예: «id가 42인 작업이 있는가?» — 예/아니오. 위치가 필요하면 거의 항상 lower_bound로 넘어갑니다.
std::lower_bound: 삽입 위치와 일치 후보
std::lower_bound(first, last, value)는 value보다 작지 않은 첫 번째 요소의 반복자를 반환합니다(operator< 관점에서). 더 사람 친화적으로 말하면: «정렬을 깨뜨리지 않도록 value를 삽입할 수 있는 위치를 보여줘»입니다.
여기서 초보자가 자주 혼동하는 점: lower_bound는 «요소 검색»이 아니라 «경계 검색»입니다. 이미 존재하는 요소의 반복자를 반환할 수도 있고, 삽입 위치를 반환할 수도 있습니다. 따라서 lower_bound 다음에는 종종 «정말 동일한가?»를 확인하는 검사가 필요합니다.
예제로 보겠습니다:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{1, 2, 4, 4, 7};
auto it = std::lower_bound(v.begin(), v.end(), 3);
std::cout << (it - v.begin()) << "\n"; // 2 (2와 4 사이)
}
값 3은 벡터에 없지만 lower_bound는 그것이 있어야 할 위치를 찾았습니다: 인덱스 2.
그리고 만약 4를 찾는다면:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{1, 2, 4, 4, 7};
auto it = std::lower_bound(v.begin(), v.end(), 4);
std::cout << (it - v.begin()) << "\n"; // 2
}
왜 인덱스가 2인가요? 그 위치는 첫 번째 4이기 때문입니다. 이는 lower_bound가 중복 처리에 유용하다는 힌트를 줍니다: 항상 동일 키 그룹의 왼쪽 경계를 가리킵니다.
std::upper_bound: 중복의 오른쪽 경계
std::upper_bound(first, last, value)는 value보다 큰 첫 번째 요소의 반복자를 반환합니다. 만약 lower_bound가 그룹의 왼쪽 경계라면 upper_bound는 오른쪽 경계(정확히는 그룹 뒤의 위치)입니다.
여러 개의 4가 있는 예를 다시 보겠습니다:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{1, 2, 4, 4, 4, 7};
auto lo = std::lower_bound(v.begin(), v.end(), 4);
auto hi = std::upper_bound(v.begin(), v.end(), 4);
std::cout << (hi - lo) << "\n"; // 3
}
여기서 (hi - lo)는 4와 동등한 요소의 개수입니다. 매우 실용적인 트릭으로, 직접 세지 않아도 되고 루프를 돌 필요도 없으며 포함/배제 문제를 헷갈리지 않습니다. STL에서 범위는 거의 항상 반개구간입니다: [lo, hi).
4. 중복에 대한 범위 [lo, hi)
컨테이너를 다루기 시작하면 «요소가 어디에 있는가»라는 질문에 익숙해집니다. 하지만 실제 데이터에서는 종종 «그 키를 가진 모든 요소는 어디인가»라는 질문이 등장합니다. 예: «상태가 Done인 모든 작업», «가격이 100인 모든 상품», «나이가 30인 모든 사람» 등. 이때 lower_bound/upper_bound 쌍은 매우 강력해집니다.
아이디어를 그림으로 고정합시다. v가 정렬되어 있고, x = 4라고 합시다:
인덱스: 0 1 2 3 4 5
v: 1 2 4 4 4 7
^ ^
lo hi
"모든 4"의 범위: [lo, hi) = 인덱스 2..4
실용적 이득: 표준화된 «관심 영역»이 생깁니다. 그 영역에 대해 무엇이든 할 수 있습니다: 출력, 집계, 처리 등. 단, 반복자를 역참조하려면 그것이 end()와 같지 않은지 확인해야 한다는 점을 잊지 마세요.
5. struct로 검색하기와 TaskBox 예제
이제 보다 현실적인 코드로 넘어갑니다. 학습용 콘솔 애플리케이션 TaskBox를 계속한다고 가정합시다 — 미니 작업 관리자입니다. 이전에는 작업을 std::vector<Task>에 저장하고 정렬한 뒤 출력했습니다. 이제 id로 작업을 빠르게 찾고 싶습니다.
모델:
#include <string>
struct Task {
int id{};
std::string title;
};
id로 정렬한다면 — 검색도 id로 하게 됩니다.
#include <algorithm>
#include <string>
#include <vector>
struct Task {
int id{};
std::string title;
};
int main() {
std::vector<Task> tasks{{2, "Read"}, {5, "Sleep"}, {3, "Code"}};
auto comp = [](const Task& a, const Task& b) { return a.id < b.id; };
std::sort(tasks.begin(), tasks.end(), comp);
}
Task에서 lower_bound로 검색하기
좋습니다. 이제 검색입니다. 함정: lower_bound는 고전적 오버로드에서 요소와 같은 타입의 value를 요구합니다. 가장 쉬운 방법은 «키 객체»를 Task{wantedId, ""}처럼 만드는 것입니다. 비교자는 오직 id만 비교하므로 문자열은 중요하지 않습니다.
#include <algorithm>
#include <string>
#include <vector>
struct Task {
int id{};
std::string title;
};
int main() {
std::vector<Task> tasks{{2, "Read"}, {3, "Code"}, {5, "Sleep"}};
auto comp = [](const Task& a, const Task& b) { return a.id < b.id; };
Task key{3, ""};
auto it = std::lower_bound(tasks.begin(), tasks.end(), key, comp);
}
하지만 it != tasks.end()라 해도 이것이 곧바로 «찾았다»를 의미하지는 않습니다. lower_bound는 삽입 위치를 반환할 수 있기 때문입니다. 따라서 id로 일치하는지 확인해야 합니다.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Task {
int id{};
std::string title;
};
int main() {
std::vector<Task> tasks{{2, "Read"}, {3, "Code"}, {5, "Sleep"}};
auto comp = [](const Task& a, const Task& b) { return a.id < b.id; };
Task key{4, ""};
auto it = std::lower_bound(tasks.begin(), tasks.end(), key, comp);
bool found = (it != tasks.end() && it->id == 4);
std::cout << found << "\n"; // 0
}
이 검사는 «의식 의식의 일부»이며 정상적인 의식 의식입니다. C++에는 많은 의식 절차가 있지만 이건 적어도 유용합니다.
정렬성 유지: find와 upsert
이제 진짜 애플리케이션 조각처럼 보이는 코드로 한 단계 나아갑시다. 우리가 원하는 두 연산은:
- 빠르게 id로 작업을 찾기.
- tasks가 id 기준으로 정렬된 상태를 유지하면서 작업을 추가하기.
두 번째가 중요한 이유는? 한 번 정렬해놓고 push_back를 하면 순서가 깨져 이진 검색을 더이상 정직하게 적용할 수 없기 때문입니다.
검색 함수를 만들어봅시다. 단순히 포인터 Task*를 반환하고(찾지 못하면 nullptr) 이전에 강의에서 nullable 계약으로서 포인터를 논의했던 것을 상기합니다.
#include <algorithm>
#include <string>
#include <vector>
struct Task {
int id{};
std::string title;
};
Task* find_task_by_id(std::vector<Task>& tasks, int id) {
auto comp = [](const Task& a, const Task& b) { return a.id < b.id; };
Task key{id, ""};
auto it = std::lower_bound(tasks.begin(), tasks.end(), key, comp);
if (it == tasks.end() || it->id != id) return nullptr;
return &(*it);
}
참고: 복잡성을 늘리지 않기 위해 반복자가 아니라 이해하기 쉬운 «있거나 없거나» 포인터를 반환합니다.
이제 추가 작업입니다. lower_bound로 삽입 위치를 찾습니다. 만약 id가 이미 존재하면 작업을 업데이트(예: title을 변경)하고, 존재하지 않으면 찾은 위치에 삽입하여 정렬을 유지합니다.
#include <algorithm>
#include <string>
#include <vector>
struct Task {
int id{};
std::string title;
};
void upsert_task(std::vector<Task>& tasks, Task t) {
auto comp = [](const Task& a, const Task& b) { return a.id < b.id; };
auto it = std::lower_bound(tasks.begin(), tasks.end(), t, comp);
if (it != tasks.end() && it->id == t.id) {
it->title = t.title; // 기존 항목을 업데이트함
} else {
tasks.insert(it, std::move(t)); // 올바른 위치에 삽입함
}
}
네, vector의 insert는 빠르지 않을 수 있습니다(요소들이 이동함). 하지만 오늘의 목표는 모델의 정확성 및 이진 검색의 올바른 적용입니다. 최적화는 다음 단계의 문제입니다(그렇지 않으면 잘못된 것을 빠르게 만드는 셈입니다).
작은 main으로 모든 것이 동작하는지 확인합시다:
#include <iostream>
#include <vector>
#include <string>
struct Task {
int id{};
std::string title;
};
Task* find_task_by_id(std::vector<Task>& tasks, int id);
void upsert_task(std::vector<Task>& tasks, Task t);
int main() {
std::vector<Task> tasks{{2, "Read"}, {5, "Sleep"}};
upsert_task(tasks, Task{3, "Code"});
upsert_task(tasks, Task{5, "Sleep more"});
Task* t = find_task_by_id(tasks, 5);
std::cout << (t ? t->title : "not found") << "\n"; // Sleep more
}
중요한 점: 삽입 후에 단 한 번도 sort를 호출하지 않았습니다. 우리는 컨테이너의 생명 주기 동안 정렬성을 유지합니다. 이는 이진 검색을 정직하게 만들고 코드의 예측 가능성을 높입니다.
6. binary_search, lower_bound, upper_bound 사용 시 흔한 실수
실수 №1: 정렬되지 않은 데이터에 이진 검색을 적용하는 것.
가장 흔한 실수입니다. 외형상 그럴듯해 보이기 때문에 더 위험합니다: 코드가 컴파일되고 프로그램은 때때로 «찾고», 때때로 «못 찾습니다», 그래서 사용자는 컴퓨터의 음모를 의심하게 됩니다. 실제로는 컴퓨터가 잘못한 것이 아니라 이진 검색이 전제로 삼는 정렬 조건을 위반했기 때문입니다. 순서가 깨져 있으면 결과는 올바르지 않을 수 있습니다.
실수 №2: 한 규칙으로 정렬하고 다른 규칙으로 검색하는 것.
첫 번째 실수의 미묘한 버전입니다. 예를 들어 Task를 id로 정렬해두고 lower_bound로 title을 찾으려 하는 경우입니다(또는 그 반대). 우연히 «맞힐» 수는 있지만 위치는 틀리게 나옵니다. 해결책은 규율입니다: 같은 비교자(또는 같은 순서)를 sort와 lower_bound/upper_bound에 사용하세요.
실수 №3: it != end()이면 찾은 것으로 간주하는 것.
lower_bound는 삽입 위치를 반환합니다. 예를 들어 4를 찾는데 벡터가 1 2 7이면 삽입 위치는 범위 내부 어딘가가 되고 it != end()는 참이 됩니다. 그러나 실제로 4는 존재하지 않습니다. 따라서 정확한 일치를 추가로 확인해야 합니다(예: it->id == wantedId).
실수 №4: end() 검사 없이 반복자를 역참조하는 것.
이 실수는 특히 교활합니다. 테스트 데이터에서는 운 좋게 통과할 수 있지만, 요소가 끝에 삽입되어야 할 때 lower_bound는 end()를 반환하고 it->id를 시도하면 큰일 납니다. 규칙은 간단합니다: 반복자는 end()와 같지 않을 때만 역참조하세요.
실수 №5: 중복을 잊고 «어떤» 요소 하나만 취하려고 하는 것.
데이터에 중복 키가 있을 수 있다면 binary_search는 단지 «있다/없다»만 알려주고, lower_bound는 왼쪽 경계만 줍니다. 의미상 모든 요소를 처리해야 한다면 올바른 모델은 범위 [lower_bound, upper_bound)입니다. 만약 lower_bound만 사용하고 하나의 요소만 가져온다면 나머지를 놓치게 되어 보고서가 맞지 않는 상황을 오래 고민하게 될 수 있습니다.
GO TO FULL VERSION