使用递归二分算法检查字符是否在字符串中

Question

我目前正在edx上编写编程课程,我的指示如下:使用二分搜索的思想,编写一个递归算法,检查字符是否包含在字符串中,只要字符串按字母顺序排列即可.我的代码(python 2.7)在这里:

def isitIn(char, aStr):
   m = aStr[len(aStr) // 2]
   if aStr == '' or len(aStr) == 1 or char == m:
      return False
   else:
      if char < m:
         return isitIn(char, aStr[:-1])
      elif char > m:
         return isitIn(char, aStr[1:])
   return isitIn(char, aStr)

我的解释:我首先找到字符串的中间字符.如果它等于字符,则返回False.如果它不等于字符,则继续检查字符是否低于中间字符,然后使用递归函数创建堆栈并最终返回布尔值True.现在我使用-1和1索引,因为我不想包含中间字符.

而不是解决方案,我宁愿得到提示,因为我仍在试图解决它,但不同的视角永远不会伤害.谢谢!

Error message:
Test: isIn('a', '')
Your output:
Traceback (most recent call last):
File "submission.py", line 10, in isIn
m = aStr[len(aStr) // 2]
IndexError: string index out of range
Correct output:
False

Answer 1

该功能永远不会返回True.我认为它应该返回True的时候char == m,所以你可以在删除它if-clause(即返回False),并把它放在另一个if:

if char == m:
   return True
elif aStr == '' or len(aStr) == 1:
    return False
else:
    ...

此外,您正在调用isIn未定义的方法.我想你想以递归的方式打电话isitIn.

比较后char < m和char > m你应该"平分"的字符串,所以不做return isitIn(char, aStr[:-1])也不是return isIn(char, aStr[1:]),而不是通过(在递归调用)的字符串的"半壁江山".

if char < m:
    return isitIn(char, aStr[:len(aStr) // 2])
elif char > m:
    return isitIn(char, aStr[len(aStr) // 2:])

编辑:以防万一,我试过的代码是:

def isitIn(char, aStr):
    if aStr == '':  # Check for empty string
        return False
    m = aStr[len(aStr) // 2]
    if char == m:
       return True
    elif len(aStr) == 1:
        return False
    else:
       if char < m:
           return isitIn(char, aStr[:len(aStr) // 2])
       elif char > m:
           return isitIn(char, aStr[len(aStr) // 2:])
    return isitIn(char, aStr)

Answer 2

总的来说,你的代码看起来很不错.但我会仔细看看你的第一个if语句.特别是,您要检查char是否等于中间字符.如果你的角色等于中间角色,你想要返回什么？

此外,您需要确保算法可以到达所有路径.在什么条件下你的函数会返回True？