5

我目前正在 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
4

4 回答 4

6

该函数永远不会返回True。我认为它应该True在 when中返回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])nor 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)
于 2014-01-14T04:44:18.737 回答
5

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

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

于 2014-01-14T04:46:28.783 回答
2

这也有效。也略短：

def isIn(char, aStr):
    if len(aStr)==0:
        return False
    elif len(aStr)==1:
        return char == aStr
    elif char == aStr[len(aStr)//2]:
        return True
    else:
        if char < aStr[len(aStr)//2]:
            return isIn(char, aStr[0:len(aStr)//2])
        elif char > aStr[len(aStr)//2]:
            return isIn(char, aStr[len(aStr)//2:]) 
    return isIn(char, aStr)
于 2017-02-02T06:32:02.287 回答
0

我认为这段代码可以正常工作，只是我在检查字符'm'之前对字符串进行了排序：

def isitIn(char, aStr):
b = ''
if aStr == '':  # Check for empty string
    return False
b = sorted(aStr)
m = b[len(b) // 2]
if char == m:
   return True
elif len(b) == 1:
    return False
elif char < m:
       return isitIn(char, b[:len(b) // 2])
else:
       return isitIn(char, b[len(b) // 2:])
return isitIn(char, aStr)
于 2017-01-22T20:32:20.087 回答