Locating a sequence in a sorted array I read the following question: Searching an element in a sorted array and I thought that I could give it a try in Python.

Given a sorted list of integers and an integer. Return the (index) bounds of the sequence of this element in the list.

Example:

l = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 6, 7, 8, 9, 9, 9, 9]

0 not found in list
1:(0, 0)
2:(1, 2)
3:(3, 5)
4:(6, 11)
5 not found in list
6:(12, 12)
7:(13, 13)
8:(14, 14)
9:(15, 18)


Here is my program (using Python 3).
It uses a dichotomic search and returns the bounds to help the search of the start and end of the sequence.

def main():
    l = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 6, 7, 8, 9, 9, 9, 9]
    print(l)
    for i in range(10):
        try:
            print(find_sequence(i, l))
        except Exception as e:
            print(str(e))


def find_sequence(x, l):
    """Return a tuple (begin, end) containing the index bounds of the sequence of x"""
    left, found, right = dichotomic_search(x, l)
    begin = outside_bound(x, l, left, found)
    end = outside_bound(x, l, right, found)
    return begin, end

def outside_bound(x, l, outside, inside):
    """Return the outside bound of the sequence"""
    if l[outside] == x:
        return outside

    middle = -1
    previous_middle = -2
    while middle != previous_middle:
        previous_middle = middle
        middle = (outside + inside) // 2
        if l[middle] == x:
            inside = middle
        else:
            outside = middle
    return inside


def dichotomic_search(x, l):
    """Return a tuple of indexes (left, found, right)

    left: leftmost index where x might be found
    found: index where x is
    right: rightmost index where x might be found
    """
    left = 0
    right = len(l) - 1

    if l[left] &gt; x or l[right] &lt; x:
        raise Exception(str(x) + ' not found in list')

    if l[left] == x:
        return left, left, right
    if l[right] == x:
        return left+1, right, right # we know that l[left]!=x

    while left &lt; right:
        middle = (left + right) // 2
        if l[middle] == x:
            return left, middle, right
        elif l[middle] &lt; x:
            left = middle + 1 # to prevent fixed point
        elif l[middle] &gt; x:
            right = middle # impossible to do -1 because of the integer division

    raise Exception(str(x) + ' not found in list')


if __name__ == "__main__":
    main()


I'm not so fond of the middle != previous_middle, but I didn't find a more elegant way (yet).
I am afraid you're approach is too complicated. Just create a function that finds the first occurrence of an element using a binary search, an another function that finds the last one. And then you can write:

def find_indexes(xs, x)
  start = find_first_index(xs, x)
  return ((start, find_last_index(xs, x, start=start)) if start else None)


For a simple implementation of find_first_index and find_last_index, check bisect.bisect_left and bisect.bisect_right source code here.