乘法二分查找算法工作原理及自定义程序时间复杂度确认

一、乘法二分查找的工作原理 #

乘法二分查找（也叫几何二分查找）是普通二分查找的变体，核心差异在中间位置的计算方式：

• 普通二分用算术平均：mid = (left + right) // 2
• 乘法二分用几何平均：mid = sqrt(left * right)

它专门针对指数分布的有序数组设计（比如元素是 a^0, a^1, a^2, ..., a^n 这类指数增长的结构）。在这类数组里，算术平均的mid会偏向左端，导致查找效率低下；而几何平均的mid能更贴近目标元素的实际位置，更快缩小查找范围。

算法流程和普通二分一致：

• 初始化左右边界left、right；
• 计算几何平均的mid；
• 对比arr[mid]和目标值：
  • 相等则返回mid；
  • arr[mid]更小，就把左边界移到mid+1，去右半区找；
  • arr[mid]更大，就把右边界移到mid-1，去左半区找；
• 重复直到区间失效（left > right），返回-1表示没找到。

二、你的代码时间复杂度验证 #

先贴出补全依赖后的代码：

import math

def multiplicative_binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = int(math.sqrt(left * right))
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1 

1. 时间复杂度结论 #

在普通均匀分布的有序数组中，最坏时间复杂度为O(log n)；在指数分布的有序数组中，时间复杂度为O(log log n)。

2. 具体推导 #

• 针对指数分布数组：比如元素是2^0, 2^1, ..., 2^10，找2^10时，几何平均的mid会直接跳到接近目标的位置，每次迭代区间的几何跨度（R/L）会减半（取平方根等价于对数减半），从初始的2^10/1缩小到1只需要log2(log2(2^10))=log2(10)≈3次迭代，也就是O(log log n)。
• 针对普通均匀分布数组：比如元素是0,1,2,...,1023，找1023时，第一次mid是0（因为left=0），之后left变成1，接下来mid依次是31、180、432、664、822、920、970、996、1010、1017、1020、1022、1023，总共14次迭代。而普通二分只需要10次，但14和10都是log2(1024)=10的常数倍，所以量级还是O(log n)。

3. 代码的小问题 #

你的代码有个边界缺陷：当left=0时，sqrt(0*right)始终是0，第一次迭代必然取mid=0，如果目标不在数组开头，这就是一次无效比较。可以改成初始left=1（数组长度>1时），或者计算mid时加个判断：mid = int(math.sqrt(left * right)) if left !=0 else (left + right)//2。

内容的提问来源于stack exchange，提问作者Sherwin Laguidao