折半查找比较次数python

折半查找的比较次数与查找的元素在有序列表中的位置有关。假设有序列表的长度为n，则最坏情况下，需要比较log2n次。以下是一个Python实现折半查找并计算比较次数的例子：

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    count = 0 # 初始化比较次数为0
    while low <= high:
        mid = (low + high) // 2
        guess = arr[mid]
        count += 1 # 每进行一次比较，次数加1
        if guess == x:
            return (mid, count)
        elif guess > x:
            high = mid - 1
        else:
            low = mid + 1
    return (None, count)

在以上代码中，`count`变量用于记录比较次数，每进行一次比较就将`count`加1。该函数返回一个元组，第一个元素是找到的元素的下标（如果找到），第二个元素是比较次数。例如，对于以下有序列表：

arr = [1, 3, 5, 7, 9]

我们可以使用如下代码进行折半查找：

index, count = binary_search(arr, 5)
print("Index:", index)
print("Comparisons:", count)

输出将会是：

Index: 2
Comparisons: 2

这表示在有序列表中找到了元素5，并且进行了2次比较。