乘法二进制搜索算法是如何工作的?

Question

我想知道我的程序有多少时间复杂度。在我看来它有一个O(log n)

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 

我试着使用chatgpt，但我有一个疑问使用它

Answer 1

我刚刚打印了一些最坏的情况:

import math
def t(n):
count=0
x=0
while(x<n):
count+=1
x=max(int(math.sqrt(x*n)),x+1)
return count
print(t(10))
print(t(100))
print(t(1000))
print(t(10000))
print(t(100000))
print(t(1000000))
print(t(10000000))
print(t(100000000))

它是O(log N)，但比二分查找差:

7
12
16
20
24
27
31
34