[Recursion and Dynamic Programming] interview questions #3

[rygh4775]

Magic Index: A magic index in an array A [e ... n -1] is defined to be an index such that A[ i] = i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A. FOLLOW UP What if the values are not distinct?

[btakeya]

def find_magic(arr):
    def go(a, start, end):
        if start > end:
            return None

        mid = int((end - start) / 2 + start)

        if a[mid] == mid:
            return mid
        elif a[mid] > mid:
            return go(a, start, mid - 1)
        else: #a[mid] < mid:
            return go(a, mid + 1, end)

    return go(arr, 0, len(arr) - 1)

if __name__ == '__main__':
    array1 = [1,3,4,8,9,11,15]
    array2 = [-5,-3,-2,0,1,2,5,7,9]
    array3 = [-2,0,2,4,7,8,10]
    print(find_magic(array1))
    print(find_magic(array2))
    print(find_magic(array3))

[btakeya]

when values are not distinct: basically, use same strategy but when mid value and mid index of each step are not same, we can narrow down range of values to search.

1. start, min(mid value, mid index - 1): e.g. mid value = 3 and mid index = 5, arr[3], arr[4] is less than or equal to 3. thus arr[3] is the only value might be equal to 3 (min(mid value, mid index - 1) -> on the other hand, index min(mid value, mid index - 1) + 1 ~ mid index can be ignored.
2. max(mid value, mid index - 1) ~ end: e.g. mid value = 5 and mid index = 3, arr[4], arr[5] is greater than or equal to 5. thus arr[3] is the only value might be equal to 5 (max(mid value, mid index + 1) -> on the other hand, index mid index ~ max(mid value, mid index + 1) + 1 can be ignored.

def find_magic_faster(arr):
    def go(a, start, end):
        if start > end:
            return None

        mid = int((end - start) / 2 + start)

        if a[mid] == mid:
            return mid
        elif a[mid] > mid:
            return go(a, start, min(a[mid], mid - 1))
        else: #a[mid] < mid:
            return go(a, max(a[mid], mid + 1), end)

    return go(arr, 0, len(arr) - 1)