python - 如何计算二分查找的步数？

Question

此代码仅返回目标的位置。我还需要计算步数。如何修改此代码以实现我的目标？

def binary_search(arr, low, high, x):
    if high >= low:
        mid = (high + low) // 2
        if arr[mid] == x:
            return mid

        elif arr[mid] > x:
            return binary_search(arr, low, mid - 1, x)

        else:
            return binary_search(arr, mid + 1, high, x)

    else:
        return -1
    
LT = [1,2,3,4,5,6,7,8,9,10]
pos = binary_search(LT,0,9,5)
print(str(pos))

标签： pythondata-structures

Answer 1

您可以将其添加为函数参数并递归更新

def binary_search(arr, low, high, x, steps = 0):

    if high >= low:
        mid = (high + low) // 2
        if arr[mid] == x:
            print(f"found at {steps} steps")
            return mid
    
        elif arr[mid] > x:
            return binary_search(arr, low, mid - 1, x, steps + 1)
    
        else:
            return binary_search(arr, mid + 1, high, x, steps + 1)
    
    else:
        return -1