为什么我的二进制搜索比线性搜索慢？
为什么我的二进制搜索比线性搜索慢？
提问于 2020-05-30 16:13:11
我试图编写一个二进制搜索和线性搜索，我震惊地发现，二进制搜索有时甚至比线性搜索慢两倍。请帮帮我。这是我的代码。
二进制搜索代码：
def binary_search(array, target, n=0):
l = len(array)-1
i = l//2
try:
ai = array[i]
except:
return False
if ai == target:
n += i
return (True, n)
elif target >= ai:
array = array[i+1:l+1]
n += i + 1
return binary_search(array, target, n)
elif target <= ai:
array = array[0: i]
return binary_search(array, target, n)线性搜索码
def linear_search(array, target):
for i, num in enumerate(array):
if num == target:
return True, i
return False测试用例代码：
import random
import time
n = 10000000
num = sorted([random.randint(0, n) for x in range(n)])
start = time.time()
print(linear_search(num, 1000000))
print(f'Linear Search: {time.time() - start}')
start_new = time.time()
print(binary_search(num, 1000000))
print(f'Binary Search: {time.time() - start_new}')回答 1
Stack Overflow用户
发布于 2020-06-07 17:06:52
正如@khelwood所说，没有切片，你的代码会更快。
def binary_search_no_slice(array, target, low, high):
if low > high:
return False
mid = (low + high) // 2
if array[mid] == target:
return True
elif array[mid] > target:
return binary_search_no_slice(array, target, low, mid - 1)
else:
return binary_search_no_slice(array, target, mid + 1, high)在下面添加到你的测试代码中。
start_new2 = time.time()
print(binary_search_no_slice(num, 1000000, 0, len(num) - 1))
print(f'Binary Search no slice: {time.time() - start_new2}')这是在我的机器上的结果(macOS Catalina，2.8 the Corei7，8 8GB内存)
False
Linear Search: 2.172485113143921
False
Binary Search: 0.56640625
False
Binary Search no slice: 2.8133392333984375e-05页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/62099645
复制相关文章
相似问题
腾讯云开发者
