二分查找数列n出现的次数和查找次数递归算法python

下面是一个递归实现的二分查找算法，可以返回数列中目标数值出现的次数和查找次数：

def binary_search_count(arr, target, left, right, count):
    if left > right:
        return 0, count  # 未找到，返回出现次数0和查找次数
    mid = (left + right) // 2
    if arr[mid] == target:
        # 在左右两侧继续查找
        left_count, count = binary_search_count(arr, target, left, mid - 1, count+1)
        right_count, count = binary_search_count(arr, target, mid + 1, right, count+1)
        return 1 + left_count + right_count, count
    elif arr[mid] < target:
        # 在右侧继续查找
        return binary_search_count(arr, target, mid + 1, right, count+1)
    else:
        # 在左侧继续查找
        return binary_search_count(arr, target, left, mid - 1, count+1)

在调用该函数时，需要传入数列、目标数值、数列的左右边界以及初始查找次数为0。调用返回后，可以得到该数值在数列中出现的次数和查找次数。

例如，对于数列`[1, 2, 2, 3, 3, 3, 4, 5, 5]`，查找数值`3`的出现次数和查找次数，可以这样调用：

arr = [1, 2, 2, 3, 3, 3, 4, 5, 5]
target = 3
count = 0
result_count, result_search = binary_search_count(arr, target, 0, len(arr)-1, count)
print("出现次数：", result_count)
print("查找次数：", result_search)

输出结果为：

出现次数： 3
查找次数： 3