수안이의 컴퓨터 연구실

원본 : http://www.debuglab.com/knowledge/upperbound.html

1.요약

C++ Standard Library의 정렬과 탐색 관련 함수 입니다.

필요하신 경우 한, 두줄의 코드를 적어주는 것 만으로도 가장 뛰어난 개발자들에의해 제작되고 테스트된 탐색 기능을 사용하실 수 있습니다

2.본문

이전 Tip에서는 O(logN)의 시간복잡도를 자랑하는 binary_search 에 대해서 알아보았습니다. binary_search 함수의 문제점은 원소가 컨테이너( 배열이나 리스트 등등..)안에 존재하는지의 유무(bool)만 반환하는 것이었으므로, 살짝 소스를 고쳐서 원소의 위치를 반환하도록 기능을 바꾸어봤습니다.

하지만 원소의 위치를 반환하는 기능이 없을리가 없겠죠. 원소의 위치를 반환하는 함수에는 upper_bound와 lower_bound가 있는데 우선은 예제를 함께 살펴보시죠.

---- upper_bound/lower_bound를 사용하는 예제 ----------

1    #include <algorithm> 

2    #include <iostream> 

3     

4    using namespace std; 

5     

6    int main(int argc, char* argv[]) 

7    { 

8        int arr[10] = {2, 6, 10, 15, 16, 17, 28, 30, 50, 52}; 

9     

10        int* pRetLowerBound = lower_bound( &arr[0], &arr[10], 16); 

11        int* pRetUpperBound = upper_bound( &arr[0], &arr[10], 16); 

12     

13        cout << "*** LowerBound ***\n"; 

14        cout << "index = " << pRetLowerBound - arr << "\n"; 

15        cout << "*pRet = " << *pRetLowerBound << endl; 

16     

17        cout << "*** UpperBound ***\n"; 

18        cout << "index = " << pRetUpperBound - arr << "\n"; 

19        cout << "*pRet = " << *pRetUpperBound << endl; 

20     

21        return 0; 

22    }

-- 실행 결과 ---------------------------------------------

*** LowerBound ***
index = 4
*pRet = 16
*** UpperBound ***
index = 5
*pRet = 17
Press any key to continue

-- 예제 분석 ---------------------------------------------

1    #include <algorithm> 

2    #include <iostream> 

3     

4    using namespace std;

C++ Standard Library 를 사용하기 위한 준비를 합니다.
upper_bound와 lower_bound는 algoritms 헤더에 있습니다.
iostream을 화면에 결과를 출력하기 위해서 추가했습니다.

-----------------------------------------------------------

8        int arr[10] = {2, 6, 10, 15, 16, 17, 28, 30, 50, 52};

아시다시피 binary search 를 수행하시려면 정렬된 데이타가 필요합니다. 잘 정렬된 int 배열이 있습니다.( 기회가 되면 다음 번엔 한 두줄로 끝나는 정렬에 대해서 살펴보도록 하죠)

-----------------------------------------------------------

10        int* pRetLowerBound = lower_bound( &arr[0], &arr[10], 16);

lower_bound 를 사용하고 있습니다. 매개변수는 3개가 필요한다. 두 개는 검색할 범위를 나타내고, 하나는 검색할 값을 나타냅니다.

STL 에서 범위를 표시하는 법은 다음과 같습니다.
시작위치 - 첫번째 원소의 주소(혹은 iterator)
마지막 위치 - 마지막 원소의 다음 원소의 주소(혹은 iterator)

마지막 위치를 지정하는 방식이 조금 특이하지만 참 유용한 방식이라는 생각이 듭니다.

다시 Line 10을 보시면서 방금 배운 내용을 적용시켜 본다면, 배열의 첫번째 원소는 a[0] 이므로 &a[0]을 넘겨주었고 마지막 원소는 a[9] 이므로 &a[10]을 넘겨주었습니다.

검색하고 싶은 값은 16입니다.

upper_bound의 경우도 사용법은 같습니다.

-----------------------------------------------------------------

나머지 코드는 단순히 결과를 출력하는 것이므로 설명은 생략하겠습니다.

upper_bound와 lower_bound 가 반환하는 값을 살펴보자면, upper_bound는 우리가 찾고자 하는 16을 지나쳐 다음 원소의 위치를 반환했습니다.

lower_bound는 우리가 찾고자 하는 16의 위치를 올바르게 반환했습니다.

lower_bound와 upper_bound의 설명은 MSDN에 나와있지만 제 실력으로는 그 의미를 추론해내기가 힘들더군요.

하지만 다른 많은 서적에는 그 의미를 훌륭하게 설명해주고 있습니다.

즉, 정렬된 컨테이너에( 다시.. 배열이나 리스트 등을 의미합니다) 새로운 원소를 대입하고 싶을때, 새 원소가 정렬을 흐트리지 않고 삽입될 수 있는 최소 경계와 최대 경계를 반환한다고 말입니다.

3.예제

4.참고

다음 함수들과 관련이 있습니다.

Binary_search, equal_range

- 2001.08.13 Smile Seo -

"C++" 카테고리의 다른 글