为什么在 python 中的这个二进制搜索代码中计数器没有增加？

Question

def binary_search(array,key,left,right):
    if left>right:
        return -1
    mid=(right+left)//2

    if key==array[mid]:
        return mid
    i=0
    if key<array[mid]:
        i+=1
        print("subarray at step {} : {}".format(i,array[left:mid]))
        return binary_search(array,key,left,mid-1)

    elif key>array[mid]:
        i+=1
        print("subarray at step {} : {}".format(i,array[mid:right]))
        return binary_search(array,key,mid+1,right)



array=[1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,222,333]
res= binary_search(array,88,0,len(array))

print(res if res!=-1 else "Not found")

在这个二进制搜索代码中，我无法弄清楚为什么计数器不工作。每次 i 打印出 1。计数器不增加。我究竟做错了什么？谢谢。

Answer 1

i 被打印为 1 因为你是 i 在每次调用时在 binary_search 函数中被设置为 0。尝试将 i 的初始化移到函数外。


def binary_search(array,key,left,right):
    global i
    if left>right:
        return -1
    mid=(right+left)//2

    if key==array[mid]:
        return mid
    # i=0
    if key<array[mid]:
        i+=1
        print("subarray at step {} : {}".format(i,array[left:mid]))
        return binary_search(array,key,left,mid-1)

    elif key>array[mid]:
        i+=1
        print("subarray at step {} : {}".format(i,array[mid:right]))
        return binary_search(array,key,mid+1,right)


i =0
array=[1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,222,333]
res= binary_search(array,88,0,len(array))

您需要更改变量 i 的范围以使其成为全局变量。

Answer 2

将i设为全局变量并赋值变量调用global关键字

i = 0
def binary_search(array,key,left,right):
    if left>right:
        return -1
    mid=(right+left)//2
    # i=0

    if key==array[mid]:
        return f'it found position {mid}'
    
    if key<array[mid]:
        global i 
        i = i+1
        print("subarray at step {} : {}".format(i,array[left:mid]))
        return binary_search(array,key,left,mid-1)

    elif key>array[mid]:
        i+=1
        print("subarray at step {} : {}".format(i,array[mid:right]))
        return binary_search(array,key,mid+1,right)



array=[1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,222,333]
res= binary_search(array,88,0,len(array))
print(len(array))

print(res if res!=-1 else "Not found")

为什么在 python 中的这个二进制搜索代码中计数器没有增加？

Why is the counter not increasing in this binary search code in python?

python

algorithm

search

counter

binary-search