def gap_binsearch(l, o=0): """binary search for a gap in a sequence takes a list l and an offset for start in the original list o""" #protect against zero element list if(len(l) == 0): return 1 #if we recurse to a one element list, we have searched to the right or left edge of the list, and must return 1 or l[0]+1 if(len(l) == 1): if(o != 0): return l[0] +1 else: return 1 mid = len(l)/2 left = mid-1 #if the left side contains a gap, we must recurse until the right side contains it or no items are left if(l[left] != o + (left + 1)): return gap_binsearch(l[:mid],o) #if both the left and right side have no gap, recurse on the right elif(l[mid] == o + (mid + 1)): return gap_binsearch(l[mid:],o+mid) #if the gap exists to the right of the midpoint, and not to the left, we have found our lowest gap else: return l[left]+1