구조체에서 lower_bound, upper_bound 사용

예를 들어,

 

struct inf {int h, c;};
imf arr[300001];

inf라는 구조체를 사용한 배열에서, lower_bound를 사용한다고 해보자.

(binary_serch로 동작하기 때문에 정렬되어 있어야 함)

 

lower_bound : 기준값 이상인 값

upper_bound : 기준값 초과인 값

 

 

h를 기준으로 lower_bound 를 찾고 싶을 때 비교 함수를 다음과 같이 작성해준다.

bool com(const inf &a, const inf &b) {
    return a.h < b.h;
}

 

찾고자 하는 인덱스를 i라고 했을 때 다음과 같이 사용하면 된다.

auto i = lower_bound(arr, arr + n, inf{arr[ix].h + s, 0}, com) - arr;

 

세번째 인자 (찾고자 하는 값)를 구조체쌍으로 써야함

네번째 인자는 비교함수