import operator


def upper_bound(x, values, cmp=operator.lt):
  """Find the last position in values
  where x could be inserted without changing
  the ordering.

  >>> values = [1, 2, 3, 3]
  >>> print upper_bound(0, values)
  0
  >>> print upper_bound(3, values)
  4
  >>> print upper_bound(4, values)
  4
  
  """
  first, count = 0, len(values)
  while count > 0:
    half = count/2
    middle = first + half
    if cmp(x, values[middle]):
      count = half
    else:
      first = middle + 1
      count = count - half - 1

  return first