import operator


def lower_bound(x, values, cmp=operator.lt):
  """Find the first position in values
  where x could be inserted without violating
  the ordering.

  >>> values = [1, 2, 3]
  >>> print lower_bound(0, values)
  0
  >>> print lower_bound(1, values)
  0
  >>> print lower_bound(1.5, values)
  1
  >>> print lower_bound(3.1, values)
  3

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

  return first