嗨,所以这里的目标是提高使用Sequential Search
在列表中查找元素所需的步骤数。
所以我有一个未排序的列表numbers = [5, 2, 1, 0, 3]
,我正在尝试查找元素3
。它需要5 steps
才能找到。
我的任务是创建一个名为sortedSequentialSearch()
的新函数,该函数以升序接收排序列表,并对其进行改进以减少查找元素3
所需的步骤。
这是我的常规顺序搜索代码:
def sequentialSearch(theValues, target):
n = len(theValues)
count = 0
for i in range(n):
count = count + 1
if theValues[i] == target:
print(f"Found, {count} steps needed")
return True
return False
如果让我说numbers.sort()
通过,该如何改善?
搜索排序数组的一种有效方法是二进制搜索。我修改了您的代码以使用它:
def binary_search(theValues, target, lower_bound, upper_bound):
middle = (upper_bound + lower_bound) // 2
if theValues[middle] == target:
return True
elif upper_bound <= lower_bound:
return False
elif target > theValues[middle]:
return binary_search(theValues, target, middle + 1, upper_bound)
else:
return binary_search(theValues, target, lower_bound, middle - 1)
另一个选项是interpolation search。如果数字是均匀分布的,平均时间为log(log(n))
,则此算法比二进制搜索更有效。最糟糕的情况是效果不佳,因为如果数字呈指数变化,则可能需要O(n)
时间。