二进制搜索 - 这是正确的吗？以及如何获得搜索词的位置

Question

我是编程初学者。我对我写的二进制搜索代码有三个问题（在 Python 中）： (1) 当我将我的代码与我在网上找到的代码进行比较时，我看到每个人都使用低值和高值参数。想知道我的代码是否有我没有看到的错误，或者只是 high/low 参数使代码更具可读性？我认为我遵循递归的思维方式（至少对我而言）。

(2) 编辑：此部分已得到回答。--->> 我无法得到 return 对或错的答案。是因为 True/False 被 returned 到递归函数而不是打印？我怎样才能得到 return 正确或错误的答案？

(3) 我想不通如何获取搜索词在列表中的位置（当然，不使用索引功能）。我以为我可以以某种方式使用代码中的“mid”变量，但不能。你能给我一些想法如何获得它在列表中的位置吗？

def binsearch(i, arr):

    mid = ((len(arr)-1)//2)

    # If we can't divide the list any further and it is not i , return false    
    if mid == 0:
        if i != arr[mid]:
            # print ("False")
            return False

    # else recursively search if i is at the mid point

    if i == arr[mid]:
        # print ("True")
        return True
    elif i < arr[mid]:
        arr = arr[0:mid+1]
        binsearch(i,arr)
    else:
        arr = arr[mid+1:]      
        binsearch(i,arr)   
i = 19
#1=1
#i=16
#i=17         
arr =[1,2,3,4,5,10,12,13,14,15,17,19]
print(binsearch(i, arr))

谢谢

阿润

Answer 1

第 2 部分的答案：您需要在 elif 和 else 语句中 return binsearch(i, arr)。

编辑：

同时回答第 3 部分，您可以将当前索引添加为 binsearch 的第三个变量，并在每次递归时更新它：

def binsearch(i, arr, index=0):

    mid = len(arr)//2
    index += mid

    # If the item is found return True and the index
    if i == arr[mid]:
        return True, index

    # i not in list
    elif not mid:
        return False

    # else recursively search if i is at the mid point
    elif i < arr[mid]:
        arr = arr[:mid]
        index -= mid

    else:
        arr = arr[mid:]

    return binsearch(i,arr, index)   
    
arr =[1,2,3,4,5,10,12,13,14,15,17,19]
for i in range(20):
    print(i, binsearch(i, arr))

输出：

0 False
1 (True, 0)
2 (True, 1)
3 (True, 2)
4 (True, 3)
5 (True, 4)
6 False
7 False
8 False
9 False
10 (True, 5)
11 False
12 (True, 6)
13 (True, 7)
14 (True, 8)
15 (True, 9)
16 False
17 (True, 10)
18 False
19 (True, 11)

Answer 2

这里的问题是您没有在递归情况下返回值。重构你的代码，它应该可以工作。

    if i == arr[mid]:
        return True
    elif i < arr[mid]:
        arr = arr[0:mid+1]
    else:
        arr = arr[mid+1:]

    return binsearch(i, arr)

二进制搜索 - 这是正确的吗？以及如何获得搜索词的位置

Binary Search - Is this correct? and how to get position of search term

python

binary-search