使用递归二分算法检查字符是否在字符串中 [英] Using a recursive bisection algorithm to check if character is in string

问题描述

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

I am currently doing the programming course over at edx and my instructions are as follows: Using the idea of bisection search, write a recursive algorithm that checks if a character is included within a string, as long as the string is in alphabetical order. My code(python 2.7) is here:

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 索引，因为我不想包含中间字符.

My explanation: I first start by finding the middle character of the string. If it equals the character, it returns False. If it does not equal the character, it goes on to check whether the character is lower than the middle character, and then using the recursive function to create the stacks and ultimately return a boolean value of True. Now I used the -1 and 1 index, as I do not want to include the middle character.

与其说是解决方案，不如说是得到提示，因为我仍在尝试解决问题，但不同的视角永远不会有什么坏处.谢谢！

Instead of a solution, I would rather get hints as I am still trying to figure it out, but a different perspective never hurts. Thanks!

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

推荐答案

函数从不返回True.我认为它应该在 char == m 时返回 True，所以你可以从 if-clause(即返回 False) 并将其放入另一个 if:

The function is never returning True. I think it should return True when char == m, so you could delete it from the if-clause(that is returning False) and put it in another if:

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

此外，您正在调用未定义的 isIn 方法.我想你想递归调用 isitIn.

Also, you are calling isIn method which is not defined. I think you wanted to recursively call isitIn.

比较后char <m 和 char >m 你应该 "bisect" 字符串，所以不要做 return isitIn(char, aStr[:-1]) 也不要 return isIn(char, aStr[1:])，而是传递(在递归调用中)字符串的一半".

After comparing char < m and char > m you should "bisect" the string, so don't do return isitIn(char, aStr[:-1]) nor return isIn(char, aStr[1:]), instead pass (in the recursive call) the "half" of the string.

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

以防万一，我试过的代码是:

Just in case, the code I've tried is:

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)

这篇关于使用递归二分算法检查字符是否在字符串中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！