我曾尝试对二进制搜索和线性搜索进行编码,但看到二进制搜索比线性搜索要慢两倍甚至两倍,我感到震惊。请帮我。这是我的代码。
二进制搜索代码:
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}')
如@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.8GHz Corei7,8GB RAM)
False
Linear Search: 2.172485113143921
False
Binary Search: 0.56640625
False
Binary Search no slice: 2.8133392333984375e-05