[STL] 8. binary_search

binary_search

std::binary_search - cppreference.com

                                         <ForwardIt>::value_type > constexpr bool binary_search( ForwardIt first, ForwardIt last,

https://en.cppreference.com/w/cpp/algorithm/binary_search

특징

• 배열이 미리 정렬이 되어 있다는 가정 하에 동작하기 때문에 사용 전 정렬이 필수이다.

• 탐색 범위 내에 값의 존재 유무를 확인해 bool값을 반환한다. 인덱스나 반복자를 반환하지 않는다.

• 이진 탐색을 수행하므로 O(log n)의 시간복잡도를 가진다.

• 정렬된 데이터에서 사용할 때 더욱 빠르고 효율적이다.

사용법

#include <algorithm>
#include <vector>
bool compare(int a, int b){
		return a > b; // 내림차순 비교
}
int main(){
		vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
		
		if(binary_search(v.begin(), v.end(), 5)) 
				cout << "true"; // 기본형
				
		if(binary_search(v.begin(), v.end(), 5, compare)
				cout << "true"; // 사용자 정의형 비교함수 사용
}