为什么 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作为全局变量并分配有价值的调用全局关键字

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")