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

Question

我目前正在 edx 上编程类(class)，我的指导如下: 使用二分搜索的思想，编写一个递归算法来检查字符串中是否包含字符，只要字符串按字母顺序排列即可。 我的代码(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。如果不等于字符，则继续检查字符是否低于中间字符，然后使用递归函数创建堆栈，最终返回 bool 值 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)