+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

暂无数据

python二进制搜索实现

发布于2020-05-29 22:13     阅读(413)     评论(0)     点赞(7)     收藏(1)


我想我做的一切都正确,但是基本情况下返回None,如果值不存在,则返回False。我不明白为什么。

def binary_search(lst, value):
    if len(lst) == 1:
        return lst[0] == value

    mid = len(lst)/2
    if lst[mid] < value:
        binary_search(lst[:mid], value)
    elif lst[mid] > value:
        binary_search(lst[mid+1:], value)
    else:
        return True

print binary_search([1,2,4,5], 15)

解决方案


您需要返回递归方法调用的结果:

def binary_search(lst, value):
    #base case here
    if len(lst) == 1:
        return lst[0] == value

    mid = len(lst)/2
    if lst[mid] < value:
        return binary_search(lst[:mid], value)
    elif lst[mid] > value:
        return binary_search(lst[mid+1:], value)
    else:
        return True

而且我认为您ifelif情况都已逆转。应该是:

if lst[mid] > value:    # Should be `>` instead of `<`
    # If value at `mid` is greater than `value`, 
    # then you should search before `mid`.
    return binary_search(lst[:mid], value)
elif lst[mid] < value:  
    return binary_search(lst[mid+1:], value)


所属网站分类: 技术文章 > 问答

作者:黑洞官方问答小能手

链接: https://www.pythonheidong.com/blog/article/397417/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

7 0
收藏该文
已收藏

评论内容:(最多支持255个字符)