def bisect_string_range(start, end):
    """Returns a string that is approximately in the middle of the range.

    (start, end) is treated as a string range, and it is assumed
    start <= end in the usual lexicographic string ordering. The output key
    mid is guaranteed to satisfy start <= mid <= end.

    The method proceeds by comparing initial characters of start and
    end.  When the characters are equal, they are appended to the mid
    string.  In the first place that the characters differ, the
    difference characters are averaged and this average is appended to
    the mid string.  If averaging resulted in rounding down, and
    additional character is added to the mid string to make up for the
    rounding down.  This extra step is necessary for correctness in
    the case that the average of the two characters is equal to the
    character in the start string.

    This method makes the assumption that most keys are ascii and it
    attempts to perform splitting within the ascii range when that
    results in a valid split.

    Args:
      start: A string.
      end: A string such that start <= end.

    Returns:
      A string mid such that start <= mid <= end.
    """
    if start == end:
      return start
    start += "\0"
    end += "\0"
    midpoint = []
    expected_max = 127
    for i in xrange(min(len(start), len(end))):
      if start[i] == end[i]:
        midpoint.append(start[i])
      else:
        ord_sum = ord(start[i]) + ord(end[i])
        midpoint.append(unichr(ord_sum / 2))
        if ord_sum % 2:
          if len(start) > i + 1:
            ord_start = ord(start[i+1])
          else:
            ord_start = 0
          if ord_start < expected_max:
            ord_split = (expected_max + ord_start) / 2
          else:
            ord_split = (0xFFFF + ord_start) / 2
          midpoint.append(unichr(ord_split))
        break
    return "".join(midpoint)
Returns a string that is approximately in the middle of the range.

    (start, end) is treated as a string range, and it is assumed
    start <= end in the usual lexicographic string ordering. The output key
    mid is guaranteed to satisfy start <= mid <= end.

    The method proceeds by comparing initial characters of start and
    end.  When the characters are equal, they are appended to the mid
    string.  In the first place that the characters differ, the
    difference characters are averaged and this average is appended to
    the mid string.  If averaging resulted in rounding down, and
    additional character is added to the mid string to make up for the
    rounding down.  This extra step is necessary for correctness in
    the case that the average of the two characters is equal to the
    character in the start string.

    This method makes the assumption that most keys are ascii and it
    attempts to perform splitting within the ascii range when that
    results in a valid split.

    Args:
      start: A string.
      end: A string such that start <= end.

    Returns:
      A string mid such that start <= mid <= end.
    
mapreduce/lib/key_range/__init__.py