Lower bound - upper bound?

Example sorted array:

	1	5	5	7
	0	1	2	3

There are four cases:
(Direction: go to higher or lower neighbor on non-match?)
(Duplicates: only for lower_bound, upper_bound never matches on equality)

Direction: forward
Duplicates: lowest index

	0	1	3	5	8	Comment
lower_bound index	0	0	1	1	4
upper_bound index	0	1	1	3	4	"lower_bound(x+1) index" (but only possible for integers)

Direction: forward
Duplicates: highest index

	0	1	3	5	8	Comment
last_lower_bound index	0	0	1	2	4	(see below)
last_upper_bound index	0	1	1	3	4	upper_bound index

Direction: reverse
Duplicates: highest index

	0	1	3	5	8	Comment
inverse_lower_bound index	-1	0	0	2	3	(upper_bound index)-1
inverse_upper_bound index	-1	-1	0	0	3	(lower_bound index)-1

Direction: reverse
Duplicates: lowest index

	0	1	3	5	8	Comment
reverse_lower_bound index	-1	0	0	1	3	(see below), not exactly (last_lower_bound index)-1
reverse_upper_bound index	-1	-1	0	0	3	(lower_bound index)-1 = inverse_upper_bound index

Some observations:

(upper_bound index)-(lower_bound index) = number of times the value occurs.
upper_bound has two directions (instead of "Duplicates"): one for "not found", and a possibly different one for "equal"; but choosing them distinct will result in discontinuities (e.g. 0 1 1 0 4).

last_lower_bound(value):
  (lb,ub) = equal_range(value)
  if (lb!=ub):
    return ub-1
  return lb    # or: return ub

Especially the reverse_lower_bound function is sometimes needed, but the STL does not provide it (well, you can use greater instead of less...):

reverse_lower_bound(value):
  (lb,ub) = equal_range(value)
  if (lb!=ub):
    return lb
  return lb-1

Let's look into in tree-based implementations:

lower_bound(key):
  var node=tree.root, ret=null
  while (node):
    if (key<=node.key):    # upper_bound has < here
      ret=node             # move this to the else branch to get inverse_upper_bound/inverse_lower_bound
      node=node.left
    else:
      node=node.right
  return ret

last_lower_bound(key):
  var node=tree.root, ret=null
  while (node):
    if (key==node.key):
      ret=node            # do this, if you want to include the value (i.e. lower_bound)
      node=node.right     # left gives you the lowest index duplicate, right the highest
                          # (if you don't include the value, .left/.right must be used for reverse/forward (?))
    else if (key<node.key):
      ret=node            # direction: forward (after else: reverse)
      node=node.left
    else:
      node=node.right
  return ret