Python二分查找函数isIn匹配特定字符返回False的问题排查

嘿，我瞅了下你写的isIn函数，问题出在递归分支的处理上，咱们一步步捋：

核心问题分析 #

你写的else块里有两个return语句，但第二个return永远不会被执行——因为第一个return已经把函数结果返回了。而且你把判断字符和中间位置字符大小关系的代码给注释掉了，导致不管目标字符是比中间字符大还是小，程序只会递归搜索字符串的左半部分，那如果目标字符在右半部分（比如你测试的"s"就在"frostbite"的右半段），自然找不到啦！

修复后的代码 #

咱们把注释的判断逻辑恢复，并且调整递归分支的处理：

def isIn(char, aStr):
    '''
    char: a single character
    aStr: an alphabetized string
    returns: True if char is in aStr; False otherwise
    '''
    if aStr == "":
        return False
    # 处理长度为1的情况，简化成一行更清晰
    if len(aStr) == 1:
        return aStr == char
    
    mid_idx = len(aStr) // 2
    mid_char = aStr[mid_idx]
    
    if mid_char == char:
        return True
    elif char < mid_char:
        # 目标字符更小，递归左半部分
        return isIn(char, aStr[:mid_idx])
    else:
        # 目标字符更大，递归右半部分（跳过已检查的中间字符）
        return isIn(char, aStr[mid_idx+1:])

# 测试你的例子
print(isIn("s", "frostbite"))  # 现在会返回True
print(isIn("i", "frostbite"))  # 返回True
print(isIn("e", "frostbite"))  # 返回True

额外优化点 #

• 把长度为1的判断简化成一行，代码更简洁
• 单独定义mid_idx和mid_char变量，提升代码可读性
• 递归右半部分时从mid_idx+1开始，避免重复检查已经判断过的中间字符（不影响结果，但能减少不必要的递归步骤）

内容的提问来源于stack exchange，提问作者code_conundrum