破解编码面试#9.3:神奇索引算法

Question

目前，我正在编写“破解编码访问”一书中的这个问题：

9.3.数组A0.n-1中的魔术索引被定义为一个索引，使得Ai = i。

这是我的密码：

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

一旦语法错误得到修复，您的代码就为我工作了，即：

• 使用[]而不是()的访问数组
• 用%而不是+调用打印

一旦这些问题得到解决，以下措施就如我所期望的那样起作用：

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

Answer 2

修正了语法错误，尝试如下：

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 or start < 0 or end >= len(seq)):
    return -1

  index = (start + end) // 2

  if(seq[index] == index):
    print("Equal to index. Value of index = %d" % index)
    return index

  if(seq[index] < index):
    print("Greater than loop. Value of Index = %d" % index)
    return magic_index(seq, index + 1, index)

  return magic_index(seq, start, index - 1)