lower_bound, upper_bound 함수 : 정렬이 되어 있다면 쓸 수 있다.

 이분 탐색을 할 때 유용한 2가지 함수를 소개해 드리고자 합니다. c++의 <algorithm> 헤더에는 lower_bound 함수가 있어요. 그리고 upper_bound 함수가 있는데요. random 접근이 가능한 경우, O(log)에 수행하게 해 주는 함수입니다.

 

 

lower_bound(first_iter,last_iter,key);

upper_bound(first_iter,last_iter,key);

 

 

 대충 요약하면 [first_iter, last_iter)에 대해서, key값보다 크거나 같은 최초의 위치, key 값보다 큰 최초의 위치를 리턴하는데요. iterator를 리턴해요. 위치를 리턴한다는 것입니다. 물론, Object를 lower_bound, upper_bound를 써야 할 경우도 종종 있는데요. 이러한 경우, compare 함수를 정의해서 쓸 수도 있어요. 이 포스팅에서는 범위를 넘어가니까 생략하도록 하겠습니다. 이 두 함수는 정렬이 되어 있다는 전제하에 쓸 수 있다는 점 유의해 주세요.

 

 

---

 예제 프로그램 1을 봅시다. 간단하게 배열을 정렬하고, lower_bound와 upper_bound를 써 보았습니다.

 

 

 저는 벡터에 3, 2, 2, 4, 5, 5를 넣었습니다. 그리고, sort를 했는데요. 그러면 vector에는 2, 2, 3, 4, 5, 5가 순서대로 저장이 되어 있을 거에요. 정렬을 했기 때문입니다.

 

 

 우리는 이분 탐색할 범위를 지정할 수 있는데요. 여기에서는 [v.begin(), v.end()) 범위 내에서 탐색합니다. 먼저 10번째 줄을 보면, key 값을 2를 주었어요. lower_bound는 2보다 같거나 큰 최초의 위치를 리턴한다고 되어 있는데요. 그 위치가 어디인가요? 노란색 부분입니다.

 

 

 따라서, 1번째 원소를 가리키는 iter를 리턴합니다. upper_bound(...,2)는 어떨까요? 이것은 탐색 범위에서 탐색을 하였을 때, key값이 2보다 큰 최초의 위치를 돌려줍니다. 그 곳은 어디인가요?

 

 

 3번째 입니다. 따라서 3번째 원소를 가리키는 iterator를 돌려주게 됩니다. 만약에, 아무리 찾아도, 범위 내에 x 이상인 것, 혹은 x 초과인 위치가 없다면 어떤 값을 리턴할까요? 이 때에는 last_iter를 리턴합니다. 여기에서는 v.end()를 last로 주었는데요. 예를 들어서, upper_bound(..,5)를 호출해 봅시다.

 

 

 그러면 5보다 큰 최초의 위치를 [v.begin(), v.end()) 범위에서 찾을 수 없어요. 그렇기 때문에 last로 넘겨준 v.end()를 돌려주게 됩니다. 이해가 가셨다면, 문제 상황을 드리겠습니다.

 

 

---

 저는 어떠한 수 x가 있는지 정렬된, 랜덤 접근이 가능한 자료구조에서 찾고 싶습니다. 이 때는 어떻게 하면 좋을까요? STL에 있는 binary_search를 쓰셔도 됩니다. 하지만 lower랑 upper를 적절하게 응용해도 됩니다. 이것은 나중에 좌표 압축을 하실 때도 꽤 유용하게 사용될 수 있는 트릭이니 알아두시면 좋겠습니다.

 

 

 먼저 x가 있는 경우를 생각해 봅시다. x가 최초로 나타난 위치를 보라색이라고 하고, x가 적혀져 있는 위치라고 한다면, lower_bound는 보라색으로 칠해졌으면서 x가 있는 위치를 가리킬 겁니다. 그러면 x보다 큰 최초의 위치는 어떻게 구해질까요? 만약에 x가 1개만 있었다면, 그 다음 원소를 가리킬 겁니다.

 

 

 2개만 있다면 어떤가요? 2칸 뒤에 있는 위치를 가리킬 거에요. 정렬되었을 때, x가 처음 등장하는 위치를 upper_bound가 가리키지는 않습니다. 이것은 자명한 사실입니다. 따라서 lower_bound(..., x)랑 upper_bound(..., x)가 돌려주는 이터레이터가 다르다면, key 값인 x는 있는 겁니다.

 

 만약에 없다면 어떨까요?

 

 

 그러면 두 영역으로 나눌 수 있습니다. x 미만인 것과, x 초과인 것. lower와 upper는 같은 곳을 가리킵니다.

 

 

 x보다 작은 데이터만 있다고 해 봅시다. 그런 경우도 탐색의 끝인 v.end()를 가리킵니다.

 

 

 x보다 큰 것들만 있다면 탐색 시작 위치를 돌려줄 거에요. x보다 큰 최초의 location과, x보다 크거나 같은 최초의 위치가 둘이 같은 셈입니다. 즉, lower랑 upper가 돌려주는 이터레이터가 같다면 x는 없는 겁니다.

 

 

 

 10815번은, 배열을 입력받고, 어떠한 수 k가 배열 안에 있는지 검사해야 하는 프로그램입니다. 13번째 줄에 sorting을 했어요. 그 이유는 이 두 함수가 정렬이 되어 있어야 제대로 동작하기 때문이에요. 그리고 18번째 줄이 제가 위에서 설명한 부분을 코드로 구현한 것인데요. key값이 a일 때, 두 함수의 리턴값이 다르다면 a가 존재하는 것이고, 아니라면 존재하지 않는 것입니다.