Find in Sorted

find_in_sorted.py

def find_in_sorted(arr, x): 
    ''' 
        Returns index of x in arr
        Precondition: arr is sorted
    '''
    def binsearch(start, end):
        mid = start + (end - start) // 2
        if start == end:
            return -1
        if x < arr[mid]:
            return binsearch(start, mid)
        elif x > arr[mid]:
            if (mid == start):
                return -1
            return binsearch(mid, end)
        else:
            return mid 
    return binsearch(0, len(arr))