[탐색] lower_bound, upper_bound

안녕하세요. BlockDMask 입니다.

오늘은  이진탐색과 유사하나 조금 다른 

lower_bound 와 upper_bound에 대해 알아보겠습니다.

1. lower_bound

• lower_bound 란?
  - 이진탐색(Binary Search)기반의 탐색 방법입니다. (배열 또는 리스트가 정렬 되어있어야 한다.)
  - lower_bound는 찾으려 하는 key값이 "없으면" key값보다 큰 가장 작은 정수 값을 찾습니다.
  - 같은 원소가 여러개 있어도 상관 없으며, 항상 유일한 해를 구할 수 있습니다.
  - 구간이 [start, end]인 배열이 있을때, 중간위치의 index를 mid 라고 하면,
  arr[mid-1] < key 이면서 arr[mid] >= key 인 최소의 m 값을 찾으면 됩니다. (m>=2)
  
  

• 직접 구현한 lower_bound 함수
  
  

  //lower_bound
  //n개로 이루어진 정수 집합에서 원하는 수 k 이상인 수가 처음으로 등장하는 위치를 찾으시오
   
  #include<iostream>
  using namespace std;
   
  int mylower_bound(int * arr, int n, int key){
      int start = 0;
      int end = n;
   
      int mid = n;
      while(end - start >0){  //start 가 end 와 같지 않고, 넘지 않을 때
          mid = (start+end)/2;    //중앙 index
   
          if(arr[mid] < key){ //key 값이 중앙 값보다 크면
              start = mid + 1;//mid 보다 오른쪽으로
          }else{  //key 값이 중앙값보다 작거나 같으면
              end = mid;  //mid 포함 왼쪽 (포함하는 이유는 key값과 같은게 없을 때 큰수중 가장 작은값을 위해)
          }
   
      }
      return end+ 1;
  }
   
  int main(void){
      int arr[10] = {1, 2, 4, 5, 6, 6, 7, 7, 7, 9};
   
      cout << "lower_bound(6) : " << mylower_bound(arr, 10, 6) << endl;
      cout << "lower_bound(7) : " << mylower_bound(arr, 10, 7) << endl;
      cout << "lower_bound(8) : " << mylower_bound(arr, 10, 8) << endl;
      cout << "lower_bound(9) : " << mylower_bound(arr, 10, 9) << endl;
      return 0;
  }

  
  

• STL 에서 제공하는 lower_bound 사용.
  
  STL에 따르면 lower_bound는 이렇게 선언 되어있습니다.
  

  template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);

  - lower_bound(arr, arr+n, key); //이런식으로 사용.
  
  

  반환형이 Iterator 이므로 vector container인 경우에는 iterator에서 v.begin()을 뺀 값으로 몇 번째 인자인지 계산을 하고,
  배열인 경우에는 배열의 첫번째 주소를 가리키는 배열의 이름을 빼면 몇 번째 인자인지 알 수 있습니다. 
  
  

  //lower_bound
  //n개로 이루어진 정수 집합에서 원하는 수 k 이상인 수가 처음으로 등장하는 위치를 찾으시오
   
  #include<iostream>
  #include<algorithm> //헤더파일
  using namespace std;
   
  int main(void){
      int arr[10] = {1, 2, 4, 5, 6, 6, 7, 7, 7, 9};
   
      cout << "lower_bound(6) : " << lower_bound(arr, arr + 10, 6) - arr + 1<< endl;
      cout << "lower_bound(7) : " << lower_bound(arr, arr + 10, 7) - arr + 1<< endl;
      cout << "lower_bound(8) : " << lower_bound(arr, arr + 10, 8) - arr + 1<< endl;
      cout << "lower_bound(9) : " << lower_bound(arr, arr + 10, 9) - arr + 1<< endl;
      return 0;
  }

• 출력 결과 
  

  두가지 경우 모두 동일한 출력이 나옵니다.

  
  

  

  
  

2. upper_bound

• upper_bound 란?
  - lower_bound와 마찬가지로 이진탐색(Binary Search)기반의 탐색법 입니다.
  - 이진탐색(Binary Search)기반이므로 배열이나 리스트가 오름차순으로 정렬 되어있어야 합니다.
  - upper_bound는 key값을 초과하는 가장 첫 번째 원소의 위치를 구하는 것 입니다.
  - 같은 원소가 여러개 존재 해도 항상 유일한 해를 구할 수 있습니다.
  - 구간이 [start, end]인 배열이 있을때, 중간위치의 index를 mid 라고 하면, 
  arr[mid-1] <= key 이면서 arr[mid] > key 인 최소의 m 값을 찾으면 됩니다. (m>=2)
  - upper_bound에서 기억해야 할 것은 (같은 값이 아닌) key 값을 초과하는 가장 첫번째 원소의 위치 라는 것 입니다.
  
  

• 직접 구현한 upper_bound 함수
  
  

  //upper_bound
  //n개로 이루어진 정수 집합에서 원하는 수 k 보다 큰 수가 처음으로 등장하는 위치를 찾으시오
   
  #include<iostream>
  using namespace std;
   
  int myupper_bound(int *arr, int n, int key){
      int start = 0;
      int end = n;
      int mid;
   
      while(end - start > 0){
          mid = (start+end)/2;
   
          if(arr[mid] <= key){    //lower_bound와 다른 점은 여기 '=' 하나
              start = mid + 1;
          }else{
              end = mid;
          }
   
      }
   
      return end +1;
  }
   
  int main(void){
      int arr[10] = {1, 2, 4, 5, 6, 6, 7, 7, 7, 9};
   
      cout << "upper_bound(6) : " << myupper_bound(arr, 10, 6)<< endl;
      cout << "upper_bound(7) : " << myupper_bound(arr, 10, 7)<< endl;
      cout << "upper_bound(8) : " << myupper_bound(arr, 10, 8)<< endl;
      cout << "upper_bound(9) : " << myupper_bound(arr, 10, 9)<< endl;
      return 0;
  }

  
  
  

• STL 에서 제공하는 lower_bound 사용.
  
  

  STL에 따르면 upper_bound는 이렇게 선언 되어있습니다.
  

  
  

  template <class ForwardIterator, class T>
  ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);

  - upper_bound(arr, arr+n, key); //이런식으로 사용. (lower_bound와 사용법은 같습니다)
  
  

  반환형이 Iterator 이므로 vector container인 경우에는 iterator에서 v.begin()을 뺀 값으로 몇 번째 인자인지 계산을 하고,
  배열인 경우에는 배열의 첫번째 주소를 가리키는 배열의 이름을 빼면 몇 번째 인자인지 알 수 있습니다. 
  
  

  //upper_bound
  //n개로 이루어진 정수 집합에서 원하는 수 k 보다 큰 수가 처음으로 등장하는 위치를 찾으시오
   
  #include<iostream>
  #include<algorithm> //헤더파일
  using namespace std;
   
  int main(void){
      int arr[10] = {1, 2, 4, 5, 6, 6, 7, 7, 7, 9};
   
      cout << "upper_bound(6) : " << upper_bound(arr, arr + 10, 6) - arr + 1<< endl;
      cout << "upper_bound(7) : " << upper_bound(arr, arr + 10, 7) - arr + 1<< endl;
      cout << "upper_bound(8) : " << upper_bound(arr, arr + 10, 8) - arr + 1<< endl;
      cout << "upper_bound(9) : " << upper_bound(arr, arr + 10, 9) - arr + 1<< endl;
      return 0;
  }

• 출력 결과
  

  

<출처>

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

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