为什么 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):&nbsp; &nbsp; global i&nbsp; &nbsp; if left>right:&nbsp; &nbsp; &nbsp; &nbsp; return -1&nbsp; &nbsp; mid=(right+left)//2&nbsp; &nbsp; if key==array[mid]:&nbsp; &nbsp; &nbsp; &nbsp; return mid&nbsp; &nbsp; # i=0&nbsp; &nbsp; if key<array[mid]:&nbsp; &nbsp; &nbsp; &nbsp; i+=1&nbsp; &nbsp; &nbsp; &nbsp; print("subarray at step {} : {}".format(i,array[left:mid]))&nbsp; &nbsp; &nbsp; &nbsp; return binary_search(array,key,left,mid-1)&nbsp; &nbsp; elif key>array[mid]:&nbsp; &nbsp; &nbsp; &nbsp; i+=1&nbsp; &nbsp; &nbsp; &nbsp; print("subarray at step {} : {}".format(i,array[mid:right]))&nbsp; &nbsp; &nbsp; &nbsp; return binary_search(array,key,mid+1,right)i =0array=[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作为全局变量并分配有价值的调用全局关键字i = 0def binary_search(array,key,left,right):&nbsp; &nbsp; if left>right:&nbsp; &nbsp; &nbsp; &nbsp; return -1&nbsp; &nbsp; mid=(right+left)//2&nbsp; &nbsp; # i=0&nbsp; &nbsp; if key==array[mid]:&nbsp; &nbsp; &nbsp; &nbsp; return f'it found position {mid}'&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; if key<array[mid]:&nbsp; &nbsp; &nbsp; &nbsp; global i&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; i = i+1&nbsp; &nbsp; &nbsp; &nbsp; print("subarray at step {} : {}".format(i,array[left:mid]))&nbsp; &nbsp; &nbsp; &nbsp; return binary_search(array,key,left,mid-1)&nbsp; &nbsp; elif key>array[mid]:&nbsp; &nbsp; &nbsp; &nbsp; i+=1&nbsp; &nbsp; &nbsp; &nbsp; print("subarray at step {} : {}".format(i,array[mid:right]))&nbsp; &nbsp; &nbsp; &nbsp; 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")