std::find와 std::binary_search의 차이

전제 조건

std::find

• 범위가 정렬되어 있지 않아도 됨
• 앞에서부터 선형으로 비교

std::binary_search

• 범위가 정렬되어 있어야 함
• 정렬된 범위에서 이분 탐색
• 정렬이 안 되어 있으면 결과가 틀릴 수 있음

시간 복잡도

std::find(first, last, value)

• O(N) (최악: 끝까지 다 봄)

std::binary_search(first, last, value)

• O(log N)

반환값

std::find

• 찾으면 그 원소를 가리키는 iterator, 못 찾으면 end 반환

auto it = std::find(v.begin(), v.end(), 7);
if (it != v.end()) { /* 위치: it */ }

std::binary_search

• 찾으면 true, 못 찾으면 false
• 존재 여부만 알려줌

bool exists = std::binary_search(v.begin(), v.end(), 7);

• 위치가 필요하면 보통 std::lower_bound를 사용

auto it = std::lower_bound(v.begin(), v.end(), 7);
bool exists = (it != v.end() && *it == 7);