std::find vs std::binary_search

std::find vs std::binary_search

std::find (선형 탐색)

• 범위의 시작 ~ 끝 까지 ‘순차적’으로 비교하며 탐색
  (선형 탐색)
  
  • O(N) 시간복잡도를 가지기에
    데이터가 늘어날수록 느려짐
    

• 데이터가 정렬되어 있지 않아도 사용가능!
  

• 발견 시, 해당 위치의 Iterator를 반환
  (발견 불가시, end() Iterator 반환)
  

• 데이터가 정렬되어 있지 않은 상황,
  너무 자주 호출하는 경우는 아니라면 사용 가능
  

#include <iostream>
#include <vector>
#include <algorithm> // std::find

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

    // 정렬하지 않고 바로 검색 가능
    auto it = std::find(v.begin(), v.end(), 5);

    if (it != v.end()) {
        std::cout << "값 찾음: " << *it << std::endl; // 위치(Iterator)를 활용 가능
    }
}

---

std::binary_search (이진 탐색)

• 탐색 범위를 절반으로 점점 나누며 탐색하는
  이진 탐색 방식
  
  • O(log n) 시간 복잡도를 가짐
    
  • 비교해야 하기에 ‘해당 타입’에 ‘비교 연산자’가
    정의되어 있어야 함!
    
• 데이터가 정렬되어 있어야 함!
  
  • 정렬되지 않은 상황에서의 호출 시,
    예상과 다른 결과가 발생 가능함
    

• 찾는 값의 존재 여부를 bool 로 반환함!
  (위치 반환 x)
  

• 데이터가 이미 정렬되어 있는 상황,
  검색이 자주 발생하는 경우, 고려 가능
  

• vector,deque,array 같은 ‘연속 메모리 컨테이너’에서 가장 좋은 효율을 발휘
  

#include <iostream>
#include <vector>
#include <algorithm> // std::binary_search, std::sort

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

    // 반드시 정렬 선행
    std::sort(v.begin(), v.end()); 

    // 존재 여부만 확인 (true/false)
    bool found = std::binary_search(v.begin(), v.end(), 5);

    if (found) {
        std::cout << "값이 존재함" << std::endl;
    }
}

정리 표

구분	std::find	std::binary_search
탐색 방식	선형 탐색	이진 탐색
시간 복잡도	O(N)	O(log N)
정렬 필요	❌ 필요 없음	✅ 정렬 필수
반환값	iterator	bool
비교 방식	==	< 기반
범위 요구	Forward Iterator 이상	Random Access Iterator

사용 가능 컨테이너 여부

컨테이너	std::find	std::binary_search
vector	✅	✅
deque	✅	✅
array	✅	✅
list	✅	❌
forward_list	✅	❌
set / map	⚠️ 가능하나 비효율	⚠️ 의미 없음
unordered_set / unordered_map	⚠️ 가능하나 비효율	❌

• list에서 binary_search는 문법상 사용 가능하지만
  사실상 find()이하의 성능이 나옴
  
  • 연결 리스트의 구조 상, Iterator가 한 칸씩만 이동할 수 있으므로
    
• set/map 은 내부적으로 ‘정렬’된 구조를 가지고 있음
  차라리 해당 컨테이너에서 지원하는 find()의 사용을 권장
  
  • 내부 트리 자료구조를 기반으로 값을 찾아 O(log N) 시간복잡도 소요
    
• unordred_set/map 은 ‘애초에’ 정렬되어 있지 않음
  find 사용이 가능하지만 역시 자체 컨테이너의 find() 사용 권장
  
  • 해시 테이블을 기반으로 값을 찾기에 O(1) ~ O(N) 시간복잡도로 소요함
    

---