Блог пользователя gXa

Binary Search
Автор gXa, история, 9 лет назад, По-английски

Can someone please explain me lower_bound and upper_bound and how they are used in sorted array? Please explain in depth.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

int* ptr = lower_bound(a, a + n, k);

returns the pointer to the first element in a that is larger than or equal to k

int* ptr = upper_bound(a, a + n, k);

returns the pointer to the first element in a that is larger than k

You can use the following to get the index. This also means "how many elements in a are smaller than k"

int index = lower_bound(a, a + n, k) - a;

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Don't forget that std::map and std::set have their own lower_bound and upper_bound function.

    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

According to cplusplus.com lower_bound(a,a+n,k) returns pointer to the first element, where k can be inserted. upper_bound(a,a+n,k) returns pointer to the last element, where k can be inserted :).

→ Ответить