本文介绍了为什么我的二进制搜索比线性搜索慢?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我试图编写二进制搜索和线性搜索的代码,看到二进制搜索有时甚至比线性搜索慢两倍,这让我感到震惊。请帮帮我。以下是我的代码。
二进制搜索代码:
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.8 GHz Corei7,8 GB内存)上的结果
False Linear Search: 2.172485113143921 False Binary Search: 0.56640625 False Binary Search no slice: 2.8133392333984375e-05更多推荐
为什么我的二进制搜索比线性搜索慢?
发布评论