破解编码面试#9.3:魔术指数算法

Question

我正在从破解编码面试的书中解决这个问题:

9.3.数组A [0 ... n-1]中的魔术索引被定义为索引,使得A [i] = i.给定一个不同整数的排序数组,编写一个方法来查找数组A中的魔术索引(如果存在).

这是我的代码:

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). 

但是,当我运行我的代码.我没有得到正确的输出.我能得到任何帮助或建议吗？提前致谢

Answer 1

一旦修复了语法错误，您的代码就对我有用，即：

• []使用not访问数组()
• %使用和不调用打印+

一旦这些问题得到解决，以下内容将按我的预期工作：

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!')

输出No Result Found对于所提供的数组来说是正确的。

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