[C++] lower_bound, upper_bound에 대하여(배열에서 key 위치 찾기)

정렬되어 있는 배열에서 이진 탐색으로 원하는 key의 인덱스를 반환해 주는 함수들이다

lower_bound: 원하는 val 값과 같거나 큰 값(이상)이 최초로 등장하는 인덱스를 반환한다

upper_bound: 원하는 val 값보다 큰 값(초과)이 최초로 등장하는 인덱스를 반환한다

 

lower_bound와 upper_bound의 코드는 아래와 같다

사실상 다른 건 다 동일하고 if문에서 이하인지 초과인지를 체크하는 부분만 다르다

// lower_bound
template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::difference_type count, step;
  count = distance(first,last);
  while (count>0)
  {
    it = first; step=count/2; advance (it,step);
    if (*it<val) {                 // or: if (comp(*it,val)), for version (2)
      first=++it;
      count-=step+1;
    }
    else count=step;
  }
  return first;
}

// upper_bound
template <class ForwardIterator, class T>
  ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::difference_type count, step;
  count = std::distance(first,last);
  while (count>0)
  {
    it = first; step=count/2; std::advance (it,step);
    if (!(val<*it))                 // or: if (!comp(val,*it)), for version (2)
      { first=++it; count-=step+1;  }
    else count=step;
  }
  return first;
}

출처: https://cplusplus.com/reference/algorithm/lower_bound/, https://cplusplus.com/reference/algorithm/upper_bound/

 

right와 left를 이용해 이분 탐색을 구현할 때와 비교하면

count(정확히는 first + count)는 right, first는 left를 의미한다고 생각하면 된다

초록색은 탐색 범위를 의미한다

위와 같은 배열에서 값(val) 5를 찾아야 한다고 가정하자. count의 값은 10이고, step은 5가 된다

advance 함수는 iterator를 이동시키는 함수로, iterator를 두번째 인자의 값만큼 뒤로 이동시킨다

 

-

 

it이 가르키는 값인 9는 val값인 7보다 작지 않으므로 else 문 내부를 실행해야 한다

 

-

 

count는 이전의 step값인 5가 되고 다시 while문 맨 위로 올라간다

it은 다시 first의 위치로 가고, step은 2가 되고, it은 2칸(step)만큼 뒤로 이동하게 된다

이때 it이 가르키는 값인 5는 val 값인 7보다 작으므로 if 문 내부를 실행한다

 

-

 

if문 내부를 실행하고 나면 위와 같이 범위가 좁혀지게 된다

 

-

 

다시 step 값을 구하고, it을 first로부터 step만큼 뒤로 보내면 위와 같아진다. 이때 *it 값이 val보다 작지 않으므로 count는 1이 된다

 

-

 

다시 step값을 구하고, step이 0이므로 it의 위치는 first와 같다. it이 가르키는 7은 val보다 작지 않으므로 count는 0이 된다

 

-

 

위와 같은 상태가 되어 while문을 탈출한다

first(7의 위치)를 리턴한다

 

 

 

만약 upper_bound라면, 앞쪽은 동일하고

해당 부분에서, it이 가르키는 7이 val인 7과 같기 때문에(*it이 val보다 크지 않기 때문에) if문 내부를 실행하게 된다

 

-

 

따라서 first가 ++it의 위치로 이동하여 7보다 큰 8의 위치를 반환하게 된다