gXa's blog

Binary Search
By gXa, history, 10 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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;

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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 :).

→ Reply