'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.'

@staticmethod
def bisect_string_range(start, end):

    if (start == end):
        return start
    start += '\x00'
    end += '\x00'
    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 = ((65535 + ord_start) / 2)
                midpoint.append(unichr(ord_split))
            break
    return ''.join(midpoint)
