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

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):&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; ln=0&nbsp; &nbsp; r = size-1&nbsp; &nbsp; mid = (ln + r) // 2&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; while (arr[mid] != val and ln <= r):&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; if val < arr[mid]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; step = step + 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; r = mid - 1&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; step = step + 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ln = mid + 1&nbsp; &nbsp; &nbsp; &nbsp; mid = (ln + r) // 2&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; if arr[mid] == val:&nbsp; &nbsp; &nbsp; &nbsp; step = step + 1&nbsp; &nbsp; &nbsp; &nbsp; return mid,step&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; return -1LT = [1,2,3,4,5,6,7,8,9,10]pos = binary_search_itr(LT,9,9)print(pos)