2

我认为我做的一切都是正确的，但是如果该值不存在，则基本情况返回 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)
4

7 回答 7

6

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

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条件是相反的。那应该是：

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)
于 2013-08-02T07:03:58.673 回答
1

因为如果什么都不返回！

if lst[mid] < value:
    binary_search(lst[:mid], value)
    # hidden return None
elif lst[mid] > value:
    binary_search(lst[mid+1:], value)
    # hidden return None
else:
    return True
于 2013-08-02T07:05:17.163 回答
1

你也需要return从if和elif。

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

>>> print binary_search([1,2,4,5], 15)
False
于 2013-08-02T07:06:08.200 回答
1

二进制搜索：

def Binary_search(num,desired_value,left,right):
    while left <= right:
        mid = (left + right)//2
        if desired_value == num[mid]:
            return mid
        elif desired_value > num[mid]:
            left = mid + 1
        else:
            right = mid - 1
    return -1
num =[12,15,19,20,22,29,38,41,44,90,106,397,399,635]
desired_value = 41
result = Binary_search(num,desired_value,0,len(num)-1)
if result != -1:
    print("Number found at " + str(result),'th index')
else:
    print("number not found")
于 2021-08-25T03:04:05.707 回答
1 
def binary_search(lists,x):
    lists.sort()
    mid = (len(lists) - 1)//2
    if len(lists)>=1:
        if x == lists[mid]:
            return True

        elif x < lists[mid]:
            lists = lists[0:mid]
            return binary_search(lists,x)

        else:
            lists = lists[mid+1:]
            return binary_search(lists,x)
    else:
        return False
a = list(map(int,input('enter list :').strip().split()))
x = int(input('enter number for binary search : '))
(binary_search(a,x))
于 2019-07-27T18:00:05.990 回答
0 
def rBinarySearch(list,element):
    if len(list) == 1:
        return element == list[0]
    mid = len(list)/2
    if list[mid] > element:
        return rBinarySearch( list[ : mid] , element )
    if list[mid] < element:
        return rBinarySearch( list[mid : ] , element)
    return True
于 2015-07-15T22:42:44.327 回答
0 
def binary_search(arr, elm):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (high + low) // 2
        val = arr[mid]
    
        if val == elm:
            return mid
        elif val <= elm:
            low = mid + 1
        else:
            high = mid - 1
        
    return -1


print(binary_search([2, 3, 4, 6, 12, 19, 20, 21], 12)) # 4
print(binary_search([2, 3, 4, 6, 12, 19, 20, 21], 3333)) # -1
于 2022-03-01T11:00:25.973 回答