upper_bound(First, Last, Val) / lower_bound(First, Last, Val)

upper_bound와 lower_bound함수는 이진 탐색을 하는 함수입니다.

자세히 말하면, upper_bound와 lower_bound는 만약 어떤 숫자가 정렬되어 있는 배열에 들어갈 때 그 숫자를 넣어도 정렬이 되어있는 상태가 되도록 하는 위치를 알려주는 함수이죠.

다음과 같은 정렬되어 있는 배열이 있다고 생각해보세요.

이 배열에 숫자 7을 넣는데 넣어도 정렬이 되고 싶다면 어디에 넣어야 할까요?

6의 다음에 오도록 하여야 하므로 이전에 9가 있던 위치를 가르킬 것입니다.

이런 상황에서는 upper_bound(), lower_bound() 모두 9가 있는 자리의 포인터를 가르킵니다.

그러면, upper_bound()와 lower_bound()의 차이점은 무엇일까요?

이 둘은 배열에 같은 숫자가 여럿일 때 차이가 나타납니다.

만약 6을 때 배열에 이미 6이 여러개 있으면 upper_bound()는 배열에 가장 끝에 있는 6의 마지막위치의 다음 위치를 가르키고

lower_bound()는 6이 가장 처음에 나타나는 위치를 가르킬 것입니다.

다음 소스는 특별히 upper_bound를 사용할 필요는 없지만 upper_bound를 사용하여 푼 문제의 소스입니다.

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &in[i]);
    sort(in + 1, in + n + 1), in[0] = -INF;
 
    scanf("%d", &q);
    while (q--) {
        scanf("%d", &x);
        w = upper_bound(in + 1, in + n + 1, x);
        printf("%d\n", *(--w) == x);
    }
}

문제 보기: 백준 1920번 - 수 찾기