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

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

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

Answer 2

Python 中的二分搜索代码，无需递归：

def binary_search_itr(arr, size, val,step=0):    

    ln=0

    r = size-1

    mid = (ln + r) // 2

    

    while (arr[mid] != val and ln <= r):        

        if val < arr[mid]:

            step = step + 1

            r = mid - 1

        else:

            step = step + 1

            ln = mid + 1

        mid = (ln + r) // 2

        

    

    if arr[mid] == val:

        step = step + 1

        return mid,step    

    return -1

LT = [1,2,3,4,5,6,7,8,9,10]

pos = binary_search_itr(LT,9,9)

print(pos)