[C++] std::find와 std::binary_search 차이 정리

C++, CS

[C++] std::find와 std::binary_search 차이 정리

dhlee-dev 2026. 5. 6. 21:41

오늘은 STL 알고리즘 중 std::find와 std::binary_search의 차이를 정리해보려고 한다.

두 함수는 모두 특정 값을 찾을 때 사용할 수 있지만 탐색 방식, 반환값, 사용 조건이 다르다.

처음에는 둘 다 단순히 값을 찾는 함수라고 생각했는데,
std::find는 순차 탐색이고 std::binary_search는 이진 탐색이라는 점에서 큰 차이가 있었다.

또한 std::binary_search는 정렬된 범위에서만 올바르게 사용할 수 있고,
컨테이너의 iterator 종류에 따라 실제 시간 복잡도가 달라질 수 있다는 점도 중요했다.

`std::find`

std::find는 범위 안에서 원하는 값을 순차 탐색으로 찾는 알고리즘이다.
즉, 처음 원소부터 마지막 원소까지 하나씩 비교하면서 값을 찾는다.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v{ 1,3,2,7,4,5 };
    int number = 4;

    auto it = std::find(v.begin(), v.end(), number);

    if (it != v.end()) {
        std::cout << number << " 찾기 성공\n";
    }
    else {
        std::cout << number << " 찾기 실패\n";
    }
}

결과는 다음과 같다.

4 찾기 성공

std::find는 값을 찾으면 해당 원소를 가리키는 iterator를 반환한다.
만약 값을 찾지 못하면 탐색 범위의 끝인 last iterator를 반환한다.

일반적으로 컨테이너 전체를 탐색할 때는 last에 container.end()를 넘기기 때문에,
값을 찾지 못한 경우 end()가 반환된다.

`std::find`의 특징

std::find의 특징은 다음과 같다.

순차 탐색으로 동작한다.
정렬되지 않은 컨테이너에서도 사용할 수 있다.
찾은 원소의 iterator를 반환한다.
찾지 못하면 last iterator를 반환한다.
시간 복잡도는 O(N)이다.
인자로 InputIterator를 받을 수 있다.

std::find는 앞에서부터 하나씩 비교하기 때문에 정렬 여부와 상관없이 사용할 수 있다.
대신 최악의 경우 모든 원소를 확인해야 하므로 시간 복잡도는 O(N)이다.

`std::binary_search`

std::binary_search는 정렬된 범위에서 원하는 값이 존재하는지 확인하는 알고리즘이다.

이진 탐색은 정렬된 범위의 중간 위치 원소를 기준으로 탐색 범위를 줄인다.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v{ 1,2,3,4,5,7 };
    int number = 4;

    bool result = std::binary_search(v.begin(), v.end(), number);

    if (result) {
        std::cout << number << " 찾기 성공\n";
    }
    else {
        std::cout << number << " 찾기 실패\n";
    }
}

결과는 다음과 같다.

4 찾기 성공

std::binary_search는 값이 존재하는지 여부만 반환한다.
따라서 반환값은 iterator가 아니라 bool이다.

값이 있으면 true, 값이 없으면 false를 반환한다.

`std::binary_search`의 사용 조건

std::binary_search를 사용하려면 탐색 범위가 정렬되어 있어야 한다.
기본적으로는 오름차순으로 정렬된 범위에서 사용한다.

std::vector<int> v{ 1,2,3,4,5,7 };

bool result = std::binary_search(v.begin(), v.end(), 4);

만약 내림차순으로 정렬된 범위에서 사용하고 싶다면
정렬 기준과 같은 비교 함수를 넘겨야 한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

int main() {
    std::vector<int> v{ 7,5,4,3,2,1 };

    bool result = std::binary_search(v.begin(), v.end(), 4, std::greater<int>());

    std::cout << std::boolalpha << result << '\n';
}

결과는 다음과 같다.

true

중요한 점은 std::binary_search에 넘기는 비교 기준과
실제 정렬 기준이 같아야 한다는 것이다.

오름차순으로 정렬했다면 기본 비교를 사용하고,
내림차순으로 정렬했다면 std::greater<T> 같은 비교 함수를 함께 넘겨야 한다.

정렬되지 않은 범위에서 사용하면 안 되는 이유

이진 탐색은 중앙값을 기준으로 탐색 범위를 줄인다.

기본적인 오름차순 기준에서는 다음과 같이 동작한다.

찾는 값이 중앙값보다 작으면 왼쪽 범위를 탐색한다.
찾는 값이 중앙값보다 크면 오른쪽 범위를 탐색한다.
중앙값과 같으면 값을 찾은 것이다.

이 방식은 데이터가 정렬되어 있다는 전제가 있어야 올바르게 동작한다.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v{ 1,3,2,7,4,5 };

    bool result = std::binary_search(v.begin(), v.end(), 4);

    std::cout << std::boolalpha << result << '\n';
}

위 코드에서 4는 실제로 vector 안에 존재한다.
하지만 vector가 정렬되어 있지 않기 때문에 std::binary_search의 결과를 신뢰할 수 없다.

즉, 원소가 있어도 찾지 못할 수 있다.

std::binary_search를 사용하기 전에는 반드시 같은 기준으로 정렬되어 있는지 확인해야 한다.

`std::binary_search`의 시간 복잡도

std::binary_search는 이진 탐색으로 동작하므로 비교 횟수는 O(log N)이다.
하지만 전체 동작 비용은 사용하는 iterator 종류에 따라 달라질 수 있다.

vector, array, deque처럼 임의 접근이 가능한 컨테이너는
중간 위치로 바로 이동할 수 있다.

개념적으로는 다음과 같은 이동이 가능하다.

auto mid = first + length / 2;

이런 식으로 it + n 연산이 가능하기 때문에 중간 위치를 빠르게 계산할 수 있다.
따라서 임의 접근 반복자를 사용하는 경우 std::binary_search는 효율적으로 동작한다.

임의 접근이 불가능한 경우

반면 list처럼 임의 접근이 불가능한 컨테이너는 it + n 연산을 사용할 수 없다.
이 경우에는 iterator를 직접 이동시켜야 한다.

auto mid = first;
std::advance(mid, n / 2);

list의 iterator는 앞뒤 이동은 가능하지만,
it + n처럼 원하는 위치로 한 번에 이동할 수는 없다.

따라서 비교 횟수 자체는 log N이지만,
중간 위치로 iterator를 이동하는 비용이 누적되어 전체 시간 복잡도는 O(N)이 될 수 있다.

즉, std::binary_search라고 해서 항상 전체 비용이 O(log N)이라고 생각하면 안 된다.

특히 list처럼 임의 접근이 불가능한 컨테이너에서는
이진 탐색의 장점이 크게 줄어들 수 있다.

iterator를 반환받고 싶다면?

std::binary_search는 값이 있는지 없는지만 알려준다.
따라서 실제 원소의 위치를 알고 싶다면 std::lower_bound나 std::upper_bound를 사용해야 한다.

`std::lower_bound`

std::lower_bound는 [first, last) 범위에서
value보다 크거나 같은 첫 번째 원소의 iterator를 반환한다.

즉, 하한선을 찾는 함수이다.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {1, 2, 2, 2, 3, 4};

    auto it = std::lower_bound(v.begin(), v.end(), 2);

    if (it != v.end()) {
        std::cout << "lower_bound 값: " << *it << '\n';
        std::cout << "인덱스: " << it - v.begin() << '\n';
    }
}

결과는 다음과 같다.

lower_bound 값: 2
인덱스: 1

2보다 크거나 같은 첫 번째 원소는 인덱스 1에 있는 2이다.
그래서 lower_bound는 해당 위치의 iterator를 반환한다.

`std::upper_bound`

std::upper_bound는 [first, last) 범위에서 value보다 큰 첫 번째 원소의 iterator를 반환한다.
즉, 상한선을 찾는 함수이다.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {1, 2, 2, 2, 3, 4};

    auto it = std::upper_bound(v.begin(), v.end(), 2);

    if (it != v.end()) {
        std::cout << "upper_bound 값: " << *it << '\n';
        std::cout << "인덱스: " << it - v.begin() << '\n';
    }
}

결과는 다음과 같다.

upper_bound 값: 3
인덱스: 4

2보다 큰 첫 번째 원소는 인덱스 4에 있는 3이다.
그래서 upper_bound는 해당 위치의 iterator를 반환한다.

중복 원소의 범위 구하기

lower_bound와 upper_bound를 함께 사용하면 중복된 값의 시작 위치와 끝 위치를 구할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {1, 2, 2, 2, 3, 4};

    auto lower = std::lower_bound(v.begin(), v.end(), 2);
    auto upper = std::upper_bound(v.begin(), v.end(), 2);

    std::cout << "2의 개수: " << upper - lower << '\n';
}

결과는 다음과 같다.

2의 개수: 3

lower_bound는 첫 번째 2를 가리키고 upper_bound는 마지막 2의 다음 위치를 가리킨다.
따라서 두 iterator 사이의 거리를 구하면 해당 값이 몇 개 있는지 알 수 있다.

단, 위 예제처럼 upper - lower를 사용하려면 해당 iterator가 임의 접근 반복자여야 한다.

list처럼 임의 접근이 불가능한 컨테이너에서는 std::distance(lower, upper)를 사용해야 한다.

`std::find`와 `std::binary_search` 비교

구분	`std::find`	`std::binary_search`
탐색 방식	순차 탐색	이진 탐색
정렬 필요 여부	필요 없음	필요함
반환값	찾은 원소의 iterator	`bool`
실패 시	`last` iterator 반환	`false` 반환
요구 iterator	Input Iterator	Forward Iterator
시간 복잡도	`O(N)`	비교 횟수는 `O(log N)`, iterator 종류에 따라 전체 비용은 달라질 수 있음
주의점	모든 원소를 순차적으로 확인	정렬 기준이 맞아야 함

std::find는 정렬되지 않은 데이터에서도 사용할 수 있지만,
앞에서부터 하나씩 확인하기 때문에 시간 복잡도는 O(N)이다.

반면 std::binary_search는 정렬된 데이터에서 빠르게 존재 여부를 확인할 수 있다.

하지만 반환값이 bool이므로 실제 위치가 필요하다면
lower_bound나 upper_bound를 사용해야 한다.

또한 임의 접근이 불가능한 컨테이너에서는
iterator 이동 비용 때문에 전체 성능이 기대보다 좋지 않을 수 있다.

정리

std::find는 정렬 여부와 상관없이 사용할 수 있는 순차 탐색 알고리즘이다.

순차적으로 값을 비교한다.
찾은 원소의 iterator를 반환한다.
찾지 못하면 last iterator를 반환한다.
시간 복잡도는 O(N)이다.
InputIterator만 만족해도 사용할 수 있다.

std::binary_search는 정렬된 범위에서 값의 존재 여부를 확인하는 알고리즘이다.

이진 탐색으로 동작한다.
반환값은 bool이다.
탐색 범위가 정렬되어 있어야 한다.
비교 기준과 정렬 기준이 같아야 한다.
ForwardIterator부터 사용할 수 있다.
비교 횟수는 O(log N)이다.
임의 접근이 불가능하면 iterator 이동 비용 때문에 전체 비용이 O(N)이 될 수 있다.

iterator를 직접 얻고 싶다면 std::binary_search가 아니라
std::lower_bound나 std::upper_bound를 사용해야 한다.

마무리

이번에 std::find와 std::binary_search를 비교하면서
단순히 값을 찾는 함수라도 내부 동작 방식과 사용 조건이 다르다는 것을 알게 되었다.

std::find는 정렬되지 않은 데이터에도 사용할 수 있지만
모든 원소를 순차적으로 확인한다.

반면 std::binary_search는 정렬된 데이터에서 빠르게 존재 여부를 확인할 수 있지만,
반환값이 bool이고 정렬 기준이 맞지 않으면 올바르게 동작하지 않을 수 있다.

또한 이진 탐색이라고 해서 항상 전체 비용이 O(log N)인 것은 아니고,
컨테이너의 iterator가 임의 접근을 지원하는지도 함께 봐야 한다.

앞으로 탐색 알고리즘을 선택할 때는
데이터가 정렬되어 있는지, 실제 위치가 필요한지,
컨테이너가 어떤 방식으로 iterator를 이동하는지까지 함께 고려해야겠다.

'C++, CS' 카테고리의 다른 글

[CS] 프로세스 간 통신 방법과 Race Condition (1)	2026.05.14
[CS] 프로세스와 스레드의 차이, Context Switching 정리 (0)	2026.05.12
[C++] STL 컨테이너 정리 (0)	2026.05.04
[C++] push_back과 emplace_back의 차이 (0)	2026.05.01
[C++] map과 unordered_map 정리 (0)	2026.04.30

현재글[C++] std::find와 std::binary_search 차이 정리

DHLee Dev Log

알고리즘, CS, 언리얼 엔진 등을 공부하며 배운 것을 기록하는 블로그입니다.

언리얼 엔진, 프로그래머스, UE5, 알고리즘, 운영체제, vtable, 단조스택, UBT, 언리얼엔진, CS, map, NGE, Binary_Search, emplace_back, UHT, 액터 컴포넌트, push_back, vptr, c++, 코딩테스트,

Today :
Yesterday :

일	월	화	수	목	금	토
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

DHLee Dev Log