C++ upper_bound, lower_bound 사용하기

 

upper_bound 와 lower_bound 함수는 정렬된 배열에서 원하는 값의 위치의 인덱스를 반환하는 함수 입니다.

 

#include <algorithm> 라이브러리에 존재합니다. 

 

사용 예시입니다. 선행조건은 꼭 정렬되어있는 배열을 넣어야합니다.

int val = lower_bound(arr, arr + n, num ) - arr ;
int val = upper_bound(arr, arr + n, num ) - arr ;

위처럼 사용하고 lower_bound는 arr배열의 0~n까지중  num값인덱스 중 제일 작은 값을 반환 합니다. 

upper_bound는 arr배열의 0~n까지중 num보다 큰 가장작은 값의 인덱스 값을 반환합니다.

 

 

즉 1 2 3 3 3 3 4 배열에서 num=2인 lowerbound는 1을 반환, upperbound는 2를 반환하는 형태입니다. (2값의 인덱스 1, 3값의 인덱스 2)

 

 

연습문제 링크:https://www.acmicpc.net/problem/3020

3020번: 개똥벌레

직접 이분탐색을 구현해서 풀어도 되지만 upper_bound, lower_bound 을 사용하는데 좋은 예제이기 때문에 가져왔습니다. 

 

문제 해설:https://gusdnr69.tistory.com/59

[백준] 3020-개똥벌레(C++)

화이팅입니다! :)