用python进行二进制搜索实现 [英] binary search implementation with python

问题描述

我认为我所做的一切都正确，但是基本情况下返回None，而不是False(如果值不存在).我不明白为什么.

I think I did everything correctly, but the base case return None, instead of False if the value does not exists. I cannot understand why.

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)

推荐答案

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

You need to return the result of the recursive method invocation:

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

我认为您的if和elif条件相反.应该是:

And I think your if and elif condition are reversed. That should be:

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)

这篇关于用python进行二进制搜索实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！