C++ / upper_bound, lower_bound ( 이분 탐색 )

upper_bound, lower_bound

이분 탐색 문제를 풀다보면 숫자를 찾는것 뿐만 아니라 개수를 새야하는 경우가 있습니다.

그럴때 사용하면 편한 함수입니다.

 

lower_bound()

배열 안에서 해당 숫자가 가장 처음으로 나온 주소를 반환합니다.

lower_bound(v1.begin(), v1.end(), x);

인덱스 번호로 사용하고 싶을땐 배열 주소를 빼 주면 됩니다.

lower_bound(v1.begin(), v1.end(), x) - v1.begin();

 

upper_bound()

배열 안에서 해당 숫자가 가장 마지막으로  나온 주소를 반환합니다.

upper_bound(v1.begin(), v1.end(), x);

똑같이 인덱스 번호로 사용하고 싶으면 배열 주소를 빼면 됩니다.

upper_bound(v1.begin(), v1.end(), x) - v1.begin();

 

 

숫자 개수 구하기

upper에서 lower를 빼준값을 사용하면 특정 숫자가 배열 안에서 몇개 들어있는지 찾을 때도 사용할 수 있습니다.

(upper_bound(v1.begin(), v1.end(), x) - v1.begin()) - (lower_bound(v1.begin(), v1.end(), x) - v1.begin());

 

예시 문제

https://lgj415415.tistory.com/68