有序搜索

问题描述 投票:0回答:2

嗨,所以这里的目标是提高使用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()通过,该如何改善?

python sequential
2个回答
1
投票

您可以在对数组进行排序后使用二进制搜索。它具有log(n)时间复杂度。

在这种情况下为2.3步,胜过3步。

https://www.geeksforgeeks.org/binary-search/


0
投票

搜索排序数组的一种有效方法是二进制搜索。我修改了您的代码以使用它:

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)时间。

© www.soinside.com 2019 - 2024. All rights reserved.