[STL 알고리즘] upper_bound, lower_bound, equal_range, binary_search

아래 함수들을 사용하기 위해선 원소들이 정렬되어 있다는 전제가 있어야 한다.

🚀 lower_bound

어떤 값의 하한선

• 이진 참색의 방법으로 어떤 값의 하한선을 찾는다.
• lower_bound(v.begin(), v.end(), 150)
  • 👉 v 컨테이너에서 Key : 150 과 일치하면 그 Key의 반복자를 리턴하고 , 일치 하는게 없다면 150을 초과하는 것 중 가장 작은 것의 반복자를 리턴한다.
• [1, 10, 20, 40, 50, 60, 70]
  • 50을 lower_bound 로 찾는다면 50의 반복자 리턴
  • 65을 lower_bound 로 찾는다면 65는 없으므로 70의 반복자 리턴
  • 80을 lower_bound 로 찾는다면 없으므로 end() 리턴

lower = lower_bound(myVector.begin(), myVector.end(), 7);

• 두 반복자로 나타낸 해당 범위 안의 원소들 중 세번째 인수 값보다 크거나 같은 첫번째 원소의 반복자를 리턴한다.
  • 없다면 범위의 끝을 나타내는 반복자를 리턴한다.
• sort와 마찬가지로 비교를 위한 비교 함수 포인터도 인자로 넣어줄 수 있다.
• 예시
  • arr = [1, 2, 3, 4, 5, 6, 7] 일때
  • lower_bound(arr, arr + 10, 6)은 6을 가리키는 반복자 이다.
    • 6 보다 크거나 같은 첫번째 원소는 6

🔥 lower_bound 를 직접 구현한 코드

int start = 0;
int end = n - 1;
 
while(start < end){  
    mid = (start + end) / 2;    
 
    if(arr[mid] < key)
        start = mid + 1;
    else
        end = mid;  
}

return end; // 시작 위치 == 끝 위치가 되면 빠져 나오며 이 위치가 바로 답이 된다. 

• Key 보다 작은 범위는 답이 될 수 없다. 👉 start = mid + 1
• Key 보다 크거나 같은 범위는 답이 될 수 있다. 그러므로 현재의 mid가 또 답 후보가 될 수 있다. 👉 end = mid
  • lower_bound 는 일치하는 것도 답이 될 수 있다.

🔥 lower_bound 에 원하는 정렬 기준 적용하기

bool comp(const string& a, const string& b) {
    if (a.length() < b.length())
        return true;
    else if (a.length() == b.length())
        if (a < b) return true;
    return false;
}

lower_bound(words.begin(), words.end(), start, comp); // comp 비교함수 기준으로 답을 찾게 됨

lower_bound는 크기 비교를 통하여 이진 탐색으로 답을 도출하는데, 이 크기 비교 즉 정렬 기준 또한 원하는대로 적용할 수 있다. sort 함수에 비교 함수 적용해주듯이 비교함수 적용해주면 된다!

위 코드를 예로 들면 1 순위로 문자열 길이를 기준으로 정렬하고 2 순위로 사전 순서로 정렬하는 비교 함수를 만들어 이를 lower_bound에 적용한 모습이다. 이제 lower_bound 는 사전 순서로 비교하기에 앞서 길이가 더 짧은 것이 더 작다고 판단하고 답을 찾게 될 것이다.

예를 들어 위 비교 함수를 적용시킨다면 이제 lower_bound는 “zzz” 가 “abcde” 보다 값이 작다고 판단할 것이다. 길이 비교가 더 우선되기 때문이다!

🚀 upper_bound

어떤 값의 상한선

• 이진 참색의 방법으로 어떤 값의 상한선을 찾는다.
• lower_bound(v.begin(), v.end(), 150)
  • 👉 v 컨테이너에서 150을 초과하는 것 중 가장 작은 것의 반복자를 리턴한다.
  • uppder_bound 는 lower_bound 와는 다르게 일치하는건 찾지 않는다.
    • lower_bound 👉 일치 or 초과하는 것 중 가장 작은 것
    • upper_bound 👉 초과하는 것 중 가장 작은 것
• [1, 10, 20, 40, 50, 60, 70]
  • 50을 upper_bound 로 찾는다면 60의 반복자 리턴 👉 lower_bound 와의 차이!
  • 65을 upper_bound 로 찾는다면 70의 반복자 리턴
  • 80을 upper_bound 로 찾는다면 없으므로 end() 리턴

upper = upper_bound(myVector.begin(), myVector.end(), 7);

• 두 반복자로 나타낸 해당 범위 안의 원소들 중 세번째 인수 값보다 큰 첫번째 원소의 반복자를 리턴한다.
  • 없다면 범위의 끝을 나타내는 반복자를 리턴한다.
• sort와 마찬가지로 비교를 위한 비교 함수 포인터도 인자로 넣어줄 수 있다.

🔥 upper_bound 를 직접 구현한 코드

int start = 0;
int end = n - 1;
 
while(start < end)){  
    mid = (start + end) / 2;    
 
    if(arr[mid] <= key) // ⭐lower_bound랑 다른점은 여기뿐!!!!!
        start = mid + 1;
    else
        end = mid;  
}

return end; // 시작 위치 == 끝 위치가 되면 빠져 나오며 이 위치가 바로 답이 된다. 

• Key 보다 작거나 같은 범위는 답이 될 수 없다. 👉 start = mid + 1
  • uppder_bound 는 lower_bound 와 다르게 일치하는 것은 답이 될 수 없음
• Key 보다 큰 범위는 답이 될 수 있다. 그러므로 현재의 mid가 또 답 후보가 될 수 있다. 👉 end = mid

🔥 upper_bound 에 원하는 정렬 기준 적용하기

upper_bound(words.begin(), words.end(), start, comp);

lower_bound와 똑같이 정의한 비교함수 파라미터로 넘겨주면 됨.

🚀 equal_range

lower_bound 와 uppder_bound 를 같이 묶어 리턴해줌

equal_range(vec.begin(), vec.end(), 3);

• (lowerbound, uppderbound)의 std::pair 객체를 리턴한다.
  • (해당 범위 내에서 처음으로 3과 같거나 큰 원소의 반복자, 해당 범위 내에서 처음으로 3보다큰 원소의 반복자)

🚀 binary_search

// 이렇게 구현되어 있다.

template <class ForwardIterator, class T>
  bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)
{
  first = std::lower_bound(first,last,val);
  return (first!=last && !(val<*first));
}

binary_search(vec.begin(), vec.end(), 3);

• bool타입을 리턴한다.
  • 즉 세번째 인수가 해당 범위 내에 있다면 true, 없으면 false를 리턴한다.

🔥 binary_search 에 원하는 정렬 기준 적용하기

비교 함수를 파라미터로 넘기면 된다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

STL 카테고리 내 다른 글 보러가기