I was having trouble finding the line segment at a distance "dist" along a LineString using shapely. This is what I came up with.

bisectLineSearch.py

def bisectLineSearch(dist, line):
    """
    Use a bisect approach to get the index of the start of the line segment that contains
    the distance specified.
    :param dist: The distance along the line
    :param line: The line in question
    :return: index along the line just before we encounter 'dist' length
    """
    arr = list(line.coords)

    def _recurse(idx, ss, count=1):
        # These are the expensive calls. We want to do them as little as possible.
        pt = Point(arr[idx])
        # Past a certain point we start decrementing instead of halving
        newss = ss / 2 if ss > 3 else ss - 1
        proj = line.project(pt)
        dir = 1 if proj < dist else -1

        # Return if we've run out of steps or we've found the culprit
        if proj == dist:
            return idx
        elif ss <= 0:
            return idx if dir > 0 else idx - 1
        else:
            return _recurse(int(idx + newss * dir), newss, count+1)

    maxind = len(arr)-1
    lineind = _recurse(maxind, maxind)
    # Note: we've got an endpoint condition here. If we're at the end of the line
    # just return the last point so we can make a valid line segment out of it.
    return lineind if lineind < maxind else lineind -1