난쿤이의 끄적끄적

정의

#include <algorithm>

헤더에 포함된 함수로 이분 검색을 실행해주는 함수다.

프로그래밍 대회에서 이분 검색을 매번 구현하는 일은 시간이 들고 또 이분 검색 구현 과정에서 실수가 생길 수 있으니 이 표준 함수를 알아두면 도움이 많이 된다.

하지만 lower_bound, upper_bound 함수의 정의에 대해 헷갈려하는 사람이 많아서 포스트를 한 번 작성해보려고 한다.

이 포스트에서는 이분 검색에 대한 기본적인 원리를 독자가 안다고 가정하므로 만약 모를 경우 이분 검색 (작성 예정) 포스트를 참고하길 바란다.

사용하기전 알아야 할 사진은 위 두 함수를 사용하기 전에 배열은 반드시 정렬되어 있어야 한다 (이는 이분 검색의 선수 조건이다).

자 그럼 lower_bound 와 upper_bound 가 무엇을 리턴하는지 알아보자.

우선, 위 함수를 사용하는 방법은 아래와 같다.

auto it = lower_bound(검색할 정렬된 배열의 첫번째 포인터, 
            검색할 정렬된 배열의 마지막 포인터 + 1, 
            찾으려고 하는 값);
auto it = upper_bound(검색할 정렬된 배열의 첫번째 포인터, 
            검색할 정렬된 배열의 마지막 포인터 + 1, 
            찾으려고 하는 값);

여기서 찾으려고 하는 값을 $target$ 이라고 하자. 

lower_bound

lower_bound 는 검색 범위내의 배열에서 $target$ 보다 작지 않은 가장 큰 (= 같거나 큰 가장 작은 원소)를 반환한다. 즉, 만약 $target$이 배열 안에 있다면 $target$을 반환할 것이고, 만약 없다면 $target$보다는 크거나 같지만 배열에서 그 전에 위치하는 원소는 $target$보다 작은 원소를 반환할 것이다. 즉, $lower\_bound() = array[i]$라고 할 때, $array[i-1] < target$, $array[i] \geq target$이다. 

만약 배열의 모든 원소가 $target$보다 작다면? 배열의 마지막 포인터 + 1 (= array.end()) 를 반환할 것이다. 따라서 이 예외처리를 하지 않고 해당 원소에 접근하려고 하려면 메모리 에러가 날 것이다. 즉 lower_bound (혹은 upper_bound) 함수로 리턴된 값이 반드시 array.end()(일반 배열일 경우 array + n) 가 아님을 확인 한 뒤 해당 원소를 접근해야한다.

upper_bound

upper_bound 는 검색 범위내의 배열에서 $target$보다 크면서 가장 작은 원소를 반환한다. 즉, $target$보다 크지만 그 전에 위치하는 원소는 $target$ 보다 작거나 큰 원소를 반환할 것이다. 즉 $upper\_bound() = array[i]$라면, $array[i-1] \geq target$이다.

여기서 lower_bound 함수와의 중요한 차이점은 만약 $target$이 배열 안에 있다고해도 $target$을 반환하는게 아니라, 그것보다 큰 바로 다음 원소를 반환한다!

그리고 lower_bound와 마찬가지로 만약 배열에 $target$보다 큰 원소가 없을 때, 배열의 마지막 포인터 + 1 (= array.end()) 를 반환할 것이다.

정리하자면, lower_bound 로 찾아진 값을 $lb$, upper_bound 로 찾아진 값을 $ub$라고 할 때

$$target \leq lb, target < ub$$

가 성립한다. 

응용

std::vector에서의 사용

만약 std::vector의 전부를 검색하고 싶으면

std::vector<T> array;
lower_bound(array.begin(), array.end(), 찾으려고 하는 값);
upper_bound(array.begin(), array.end(), 찾으려고 하는 값);

과 같이 .begin(), .end() 포인터 (=Iterator)를 사용하면 된다. 일반 배열의 경우는 array.begin() 대신에 array 를 (배열의 첫번째 주소를 가리키는 포인터), array.end() 대신에 array + n (n 은 배열의 크기)를 사용하면 된다.

만약 인덱스 i 와 j까지만 검색하고 싶다면 ($i < j$)

std::vector<T> array;
lower_bound(array.begin() + i, array.begin() + j, 찾으려고 하는 값);
upper_bound(array.begin() + i, array.end() + j, 찾으려고 하는 값);

와 같이 인덱스를 덧셈해서 사용하면 된다. 

그럼 lower_bound 와 upper_bound 함수는 무엇을 리턴할까?

아래 코드를 다시 보자

auto it = lower_bound(검색할 정렬된 배열의 첫번째 포인터, 
    검색할 정렬된 배열의 마지막 포인터 + 1, 
    찾으려고 하는 값);
auto it = upper_bound(검색할 정렬된 배열의 첫번째 포인터, 
    검색할 정렬된 배열의 마지막 포인터 + 1, 
    찾으려고 하는 값);

위와 같이 사용하면 it 에는 포인터 (Iterator)값이 들어가는데 포인터값이 아닌 인덱스를 알고 싶다면 it에서 배열의 첫번째 원소의 포인터를 빼주면 된다. 즉, std::vector 라면

std::vector<T> array;
int index = 
	lower_bound(array.begin(), array.end(), 찾으려고 하는 값) 
    	- array.begin();
int index = 
	upper_bound(array.begin(), array.end(), 찾으려고 하는 값) 
    	- array.begin();

을 하면 된다. 일반 배열의 경우는 마찬가지로 배열의 포인터 (= array)를 빼주면 된다.

이분검색에서의 활용

1) 만약 어떤 원소 $target$을 찾고 싶다면 $lower_bound$ 함수를 호출 한뒤 위에 설명된 방식대로 인덱스를 구하면 된다. 단, 함수의 리턴값이 array.end() 라면 $target$을 찾지 못한것이니 메모리 에러가 나지 않도록 주의하자.

2) 만약 어떤 원소 $target$보다 작은 원소중 가장 큰 원소를 찾고 싶다면 $lower_bound$ 함수를 호출 한뒤 위 방식대로 인덱스를 구하고 1을 빼주면 된다 (함수의 리턴값이 array.end() 라도 그냥 -1을 빼주면 된다. 왜냐하면 이뜻은 모든 원소가 다 $target$보다 작다는 의미이므로 마지막 인덱스의 원소가 $target$보다 작으면서 제일 크다).

2) 만약 어떤 원소 $target$보다 큰 원소중 가장 작은 원소를 찾고 싶다면 $upper_bound$ 함수를 호출 한뒤 위 방식대로 인덱스를 구하면 된다. 함수의 리턴값이 array.end() 라면 $target$보다 큰 원소가 없다는 의미이다.

만약 위 두 함수에 대해 더 알아보고 싶으면 아래 공식 레퍼런스를 참고하라.

참고: http://www.cplusplus.com/reference/algorithm/lower_bound/

http://www.cplusplus.com/reference/algorithm/upper_bound/