唔明二分法搜索和递归

Question

这里是我试图环绕我的头问题：

我们可以使用二分法搜索的理念，以确定是否一个字符 是一个字符串，那么长因为字符串按字母顺序排序。

首先，根据您要查找的字符 测试字符串的中间字符（“测试字符”）。如果他们是一样的，我们 完成 - 我们找到了我们正在寻找的角色！

如果它们不相同，请检查测试字符是否比中间字符“ ”小。如果是这样，我们只需要考虑字符串的下半部分 ;否则，我们只考虑字符串的上半部分。 （请注意，您可以使用Python的<功能比较字符）。

实现函数伊辛（字符，而aStr）的递归实现上述 想法来测试是否char是在而aStr。 char将是一个单一的 字符，而aStr将是一个按字母顺序排列的字符串。 函数应该返回一个布尔值。

当您设计功能时，请仔细考虑基底 应该是什么。

这是我试过的代码。我遇到了错误，但我在理解如何解决这个问题的基础知识方面落伍了。就落伍

def isIn(char, aStr): 
    ''' 
    char: a single character 
    aStr: an alphabetized string 

    returns: True if char is in aStr; False otherwise 
    ''' 
    # Your code here 
    middle_char = len(aStr)/2 
    if char == middle_char: 
     True 
    elif char == "" or char == 1: 
     False 
    elif char < aStr[:middle_char]: 
     return isIn(char,aStr(middle_char) 
    else: 
     return isIn(char, aStr(middle_char)) 

Answer 1

的原因之一是，你想写一个递归函数，当你还没有掌握编写简单的语句。这里有大约10行活动代码，包括至少4个语法错误和2个语义错误。

后退并使用增量编程。写几行代码，测试它们，直到你确定它们按预期工作为止。插入诊断print语句以随时检查值。例如，开始强行喂食的价值观和没有实际的函数调用，就像这样：

# def isIn(char, aStr): 
''' 
char: a single character 
aStr: an alphabetized string 

returns: True if char is in aStr; False otherwise 
''' 

char = 'q' 
aStr = "abcdefghijklmnopqrstuvwxyz" 
print "parameters:", char, aStr 

middle_char = len(aStr)/2 
print len(aStr), middle_char 

print "if", char, "==", middle_char, ":" 

这给你输出

parameters: q abcdefghijklmnopqrstuvwxyz 
26 13 
if q == 13 : 

显然，一个字符是不要等于整数13. 解决这个问题之前，你走得更远。 然后你可以尝试写下你的第一个if声明。

看看如何工作？

Answer 2

middle_char = len(aStr)/2 
if char == middle_char: 

中东char是长度的一半（即整数值） 这不会等于你的char值。

middle_index = len(aStr)//2 
middle_char = aStr[middle_index] 

实际上得到中间char值。请注意整数除法（//）。我们希望确保所得到的索引是一个整数。

elif char == "" or char == 1: 

你已经测试过（很好地尝试过）只剩下一个字符的情况，你不需要特别处理。您还需要在之前测试空字符串，然后尝试提取值。

elif char < aStr[:middle_char]: 

在这里你实际上尝试和索引到字符串。不幸的是，你实际上在做的是切片，看看字符串（中间字符向前）的secind是否等于你的char。这只会在您查看一个字符字符串时匹配。例如isin('d', 'd')

return isIn(char,aStr(middle_char) 
else: 
    return isIn(char, aStr(middle_char)) 

- 缺少括号第一回) - aStr()不是一个函数。您需要[和] - 您试图将单个字符传递给递归调用。您需要对字符串进行切片，并将生成的子字符串传递给递归字符串 - 这两个（忽略缺少的括号）都是相同的调用。你需要一个打电话给aStr的前半部分和下半部分。

你的任务说要考虑基本情况。他们是（我列出他们，因为你几乎把他们点上）： - 空字符串（返回False） - mid char =搜索字符（返回True） - mid char>搜索char（搜索左字符串） - 中期焦炭<搜索字符（搜索右子）

请注意，有没有必要明确地检查非匹配字符串的长度1，因为这将传递一个空字符串到下一个电话

东西让你思考一下：为什么字符串需要排序？如果字符串不被排序会发生什么？

工作实施：

def isin (char, str): 
    if not str: 
     return False 
    mid_index = len(str)/2 
    mid_char = str[mid_index] 
    return True if mid_char == char else isin(char, str[:mid_index] if mid_char > char else str[mid_index+1:]) 

不要只需使用此代码。这段代码仅供您参考，因此您可以理解它在做什么，并在理解后重新编写代码。如果你不了解它，那么只需复制代码就没有意义。它不会在未来帮助你。

你似乎对你需要做的事情有一般的想法（我猜你已经在课堂上了解了这一点），但在如何（语法等）方面缺乏知识。

我建议你在自己的时间通过the python tutorial，做你需要做的练习。它会依次向您介绍该语言的功能，这将对您有所帮助。

祝你好运！