[1] Note that you may use an ordering that is a strict weak ordering but not a total ordering; that is, there might be values x and y such that x < y, x > y, and x == y are all false. (See the LessThan Comparable requirements for a more complete discussion.) Finding value in the range [first, last) , then, doesn't mean finding an element that is equal to value but rather one that is equivalent to value: one that is neither greater than nor less than value . If you're using a total ordering, however (if you're using strcmp, for example, or if you're using ordinary arithmetic comparison on integers), then you can ignore this technical distinction: for a total ordering, equality and equivalence are the same.

[2] If an element that is equivalent to [1] value is already present in the range [first, last), then the return value of lower_bound will be an iterator that points to that element.

[3] This difference between Random Access Iterators and Forward Iterators is simply because advance is constant time for Random Access Iterators and linear time for Forward Iterators.