[C/C++] lower_bound, upper_bound, binary_search 사용법

배열에서 특정한 수를 찾거나, 특정한 수가 몇 개 있는지, 좌표 압축 중복 제거 등에 자주 사용

 

#include <iostream>
#include <vector>
#include <algorithm> // lower_bound와 upper_bound는 <algorithm> 헤더 안에 존재 
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int arr[] = {40, 30, 30, 20, 40, 10};
    vector<int> v(arr, arr + 6);
    
    cout << "정렬 전 : ";
    for(int i = 0; i < v.size(); i++) {
    	cout << v[i] << " ";
	} 
	cout << "\n"; 
    
    // binary search 기반이므로, 정렬된 상태여야함 
    sort(v.begin(), v.end()); // 10, 20, 30, 40, 50, 60
    
    cout << "정렬 후 : ";
    for(int i = 0; i < v.size(); i++) {
    	cout << v[i] << " ";
	} 
	cout << "\n";
    
    // 시작 이터레이터 ~ 끝 이터레이터 사이에서 value 이상/초과인 값을 가지는 이터레이터 반환 
    // 인덱스 반환을 하려면 시작 이터레이터 값을 빼준다. 
    cout << lower_bound(v.begin(), v.end(), 30) - v.begin() << "\n"; // 벡터 v에서 30 이상인 수의 인덱스를 출력 
	cout << upper_bound(v.begin(), v.end(), 30) - v.begin() << "\n"; // 벡터 v에서 30 초과인 수의 인덱스를 출력 
}

 

// 존재하면 1을 반환하고, 없다면 0을 반환
cout << binary_search(시작 이터레이터, 끝 이터레이터, 찾을 거);