[탐색 알고리즘] lower_bound, upper_bound

안녕하세요.

playground입니다.

이번에 알아볼 내용은 탐색 알고리즘 함수 lower_bound, upper_bound에 대해 알아보겠습니다.

먼저 이 두 함수는 이진탐색 기반의 함수이고, 정렬된 리스트로 가정하고 쓸 수 있는 함수입니다.

 

---

- lower_bound 함수

template <class _FwdIt, class _Ty> _FwdIt lower_bound(_FwdIt first, _FwdIt last, const _Ty& value);

 

- [범위 first, 범위 last] 중에서 value(키값)와 같거나 큰 최초의 위치를 반환

 

예를 들어 

[1, 3, 5, 7, 7] 이라는 범위를 리스트가 있고 찾으려는 키값이 7이라면

빨간색 화살표 위치인 주소값을 반환합니다.

 

---

 

- lower_bound 예제

 

한 번 lower_bound 함수를 써보겠습니다.

 

#include <iostream> #include <algorithm> using namespace std; const int iMAX = 100000000; int iCount, k;  int iArr[iMAX] = {}; int main() {      setbuf(stdout, NULL);      scanf("%d", &iCount);      for (int i = 0; i < iCount; ++i)           scanf("%d", &iArr[i]);      scanf("%d", &k);      // lower_bound      int* a = lower_bound(iArr, iArr + iCount, k);      // 아래와 같이 해야 원하는 자리값을 구할 수 있다.      // int a = lower_bound(iArr, iArr + iCount, k) - iArr + 1; }

 

입력

1 3 5 7 7 이 값을 넣어주고 찾으려는 값은 7라고 해보겠습니다.

 

위와 같이 lower_bound 함수에

첫번째 인자값에는 배열의 첫번째 주소,

두번째 인자값에 마지막 주소값,

세번째 인자값에 찾고 싶은 key값을 넣어줍니다.

 

 

출력

 

lower_bound 함수는 주소값을 리턴하기 때문에 a를 포인터변수로 받아서 확인해봤습니다.

위 코드를 디버깅하면 a는 [1 3 5 7 7]배열 중에서 iArr[3] 주소값(값 : 7)이 된 걸 확인할 수 있습니다. 

만약에 원하는 위치를 반환하게 하고 싶으면 아래와 같은 코드여야 됩니다.

 

 

int a = lower_bound(iArr, iArr + iCount, k) - iArr + 1;

 

 

해당 주소값에서 배열 첫번째 주소값을 빼면 차이값이 나오는데 보통은 첫번째를 1부터 시작하므로 1을 더해줍니다.

이러면 원하는 자리값을 구할 수 있습니다.

 

---

- lower_bound 직접 구현하기

int lower_bound(int _s, int _e) {      while (_e - _s > 0)      {           int m = (_s + _e) / 2;           if (iArr[m] < k)                _s = m + 1;           else                _e = m;      }      return _e + 1; }

주소값을 리턴하는 함수는 아니지만 lower_bound 기능을 하는 함수입니다.

 

 

 

 

---

- upper_bound 함수

 

template <class _FwdIt, class _Ty> _FwdIt upper_bound(_FwdIt first, _FwdIt last, const _Ty& value);

 

 

- [범위 first, 범위 last] 중에서 value(key값)보다 큰 수가 처음으로 등장하는 위치 찾는 함수

 

예를 들어 

[1, 3, 5, 7, 8] 이라는 범위를 리스트가 있고 찾으려는 키값이 7이라면 7 다음 수인

빨간색 화살표 위치인 주소값을 반환합니다.

 

---

- upper_bound  예제

 

#include <iostream> #include <algorithm> using namespace std; const int iMAX = 100000000; int iCount, k;  int iArr[iMAX] = {}; int main() {      setbuf(stdout, NULL);      scanf("%d", &iCount);      for (int i = 0; i < iCount; ++i)           scanf("%d", &iArr[i]);      scanf("%d", &k);      // upper_bound      int* a = upper_bound(iArr, iArr + iCount, k);      // 아래와 같이 해야 원하는 자리값을 구할 수 있다.      // int a = upper_bound(iArr, iArr + iCount, k) - iArr + 1; }

 

입력

1 3 5 7 8 이 값을 넣어주고 찾으려는 값은 7라고 해보겠습니다.

 

 

출력

lower_bound 함수는 주소값을 리턴하기 때문에 a를 포인터변수로 받아서 확인해봤습니다.

위 코드를 디버깅하면 a는 [1 3 5 7 8]배열 중에서 iArr[4] 주소값(값 : 8)이 된 걸 확인할 수 있습니다. 

 

---

- upper_bound 직접 구현하기

int upper_bound(int _s, int _e) {      while (_e - _s > 0)      {           int m = (_s + _e) / 2;           if (iArr[m] <= k)                _s = m + 1;           else                _e = m;      }      return _e + 1; }

 

 

 

이번 포스팅에서는 lower_bound, upper_bound에 대해 알아봤습니다.

읽어주셔서 감사합니다.