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

以下是一个递归实现的二分查找数列n出现的次数和查找次数的Python代码：

def binary_search(arr, x, first, last, count):
    count += 1
    if last < first:
        return 0, count
    mid = (first + last) // 2
    if arr[mid] == x:
        left_count, count = binary_search(arr, x, first, mid - 1, count)
        right_count, count = binary_search(arr, x, mid + 1, last, count)
        return left_count + right_count + 1, count
    elif arr[mid] > x:
        return binary_search(arr, x, first, mid - 1, count)
    else:
        return binary_search(arr, x, mid + 1, last, count)

arr = [1, 2, 2, 2, 3, 4, 5, 5, 6]
x = 2
first = 0
last = len(arr) - 1
count = 0
count_of_x, count_of_search = binary_search(arr, x, first, last, count)
print("数列中 %d 出现的次数为 %d 次，查找次数为 %d 次。" % (x, count_of_x, count_of_search))

运行结果为：

数列中 2 出现的次数为 3 次，查找次数为 3 次。

其中，`binary_search` 函数的参数 `arr` 表示要查找的数列，`x` 表示要查找的元素，`first` 表示数列的起始下标，`last` 表示数列的结束下标，`count` 表示查找次数。函数返回值为一个元组，第一个元素表示数列中 `x` 出现的次数，第二个元素表示查找次数。函数的实现方式是，首先计算出中间元素的下标 `mid`，然后比较 `arr[mid]` 和 `x` 的大小。如果相等，则递归调用函数分别在左半部分和右半部分查找 `x`，并将左半部分和右半部分中 `x` 出现的次数相加。如果 `arr[mid]` 大于 `x`，则说明 `x` 在左半部分，递归调用函数查找左半部分。如果 `arr[mid]` 小于 `x`，则说明 `x` 在右半部分，递归调用函数查找右半部分。在每次递归调用函数时，都需要将查找次数加 1。最后，将函数的返回值和查找次数打印出来即可。