organisedChaos's blog

By organisedChaos, history, 2 months ago, In English

Brief overview:-

The functions upper_bound() and lower_bound() functions are useful when we have data stored in a non-decreasingly sorted format and in a given range in the data structure we want to find out:

  1. position of the smallest number just > (greater) a given number
  2. position of the smallest number >= (greater than or equal to) a given number

we can use these 2 functions.

Lets take an example data and understand:- vector<int> a = {5,6,9,9,10,15,19,25};

upper_bound() :-

  • returns an iterator pointing to the element just greater than the given number
  • upper_bound of:
  1. 5 will give an iterator pointing to 6 located at index 1.
  2. 9 will give an iterator pointing to 10 located at index 5.
  3. 2 will give an iterator a.begin() i.e., element 5 located at index 0.
  4. 25 will give an iterator a.end() as there is no such element > 25 in the list.

lower_bound() :-

  • returns an iterator pointing to the element greater than or equal to the given number
  • lower_bound of
  1. 15 will give an iterator pointing to 15 located at index 5.
  2. 9 will give an iterator pointing to 9 located at index 2. (will give the leftmost occurrence in case of multiple data)
  3. 2 will give an iterator a.begin() i.e., element 5 located at index 0.
  4. 30 will give an iterator a.end() as there is no such element >= 30 in the list.
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by organisedChaos (previous revision, new revision, compare).