Magic Index CS 61A Spring 2015

Question | Magic Index

A magic index in a list A[0...n-1] is defined to be an index such that A[i] = i. Given a sorted list, write a function to find a magic index, if one exists, in list A. Fill in the blanks below so the doctests pass.

def magic_index(lst):
    """ 
    >>> magic_index([1, 2, 3, 3, 4])
    3
    >>> magic_index([1, 1, 2, 5, 6])
    2
    """ 
    return finder(lst, 0, len(lst) - 1)

def finder(lst, low, high):
    mid = (low + high) // 2
    if ________:
        return ________
    if ________:
        return ________
    else:
        return ________

def magic_index(lst):
    """ 
    >>> magic_index([1, 2, 3, 3, 4])
    3
    >>> magic_index([1, 1, 2, 5, 6])
    2
    """ 
    return finder(lst, 0, len(lst) - 1)

def finder(lst, low, high):
    mid = (low + high) // 2
    if lst[mid] == mid: 
        return mid
    if arr[mid] > mid: 
        return finder(lst, mid + 1, high) 
    else:
        return finder(lst, low, mid - 1)