Cracking the coding interview #9.3: magic index algorithm [closed]

Question

I am currently doing this problem from the book cracking the coding interview:

9.3. A magic index in an array A[0...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.

And here is my code:

def magic_index(seq, start = None, end = None):
    if start is None:
        start = 0

    if end is None:
        end = len(seq) - 1

    if start > end:
        return -1

    index = (start + end) // 2
    if index == seq(index):
        print("Equal to index. Value of index = " + index)
        return index

    if index > seq[index]:
        print("Greater than loop. Value of Index =" + index)
        return magic_index(seq, start=index + 1, end=end)
    else:
        print("Else part of Greater. Value of index = " + index)
        return magic_index(seq, start=start, end=index - 1)


def main():
    magic_index(seq=[1, 2, 3, 4, 6], start=None, end=None). 

However, when i run my code. I am not getting the proper output. Is there any help or advice I could get? Thanks in advance

Answer 1

Your code worked for me once the syntax errors were fixed, namely:

• Access arrays using [] not ()
• Call print with % and not +

Once those are fixed, the following worked as I would expect:

def magic_index(seq, start = None, end = None):
    if start is None:
        start = 0

    if end is None:
        end = len(seq) - 1

    if start > end:
        return -1

    index = (start + end) // 2
    if index == seq[index]: # array indexing with `[]` not `()`
        print("Equal to index. Value of index = %s" % index) # use % to print index
        return index

    if index > seq[index]:
        print("Greater than loop. Value of Index = %s" % index)
        return magic_index(seq, start=index + 1, end=end)
    else:
        print("Else part of Greater. Value of index = %s" % index)
        return magic_index(seq, start=start, end=index - 1)


def main():
    result = magic_index(seq=[1, 2, 3, 4, 6], start=None, end=None)
    if result == -1:
        print('No Result Found!')

The output was No Result Found which is correct for the provided array.

print magic_index(seq=[0, 1, 2, 3, 4, 5], start=None, end=None)
# prints 2
print magic_index(seq=[0, 2, 4, 6], start=None, end=None)
# prints 0