python - 排序顺序搜索

Question

嗨，这里的目标是改进使用Sequential Search.

所以我有一个未排序的 List numbers = [5, 2, 1, 0, 3]，我试图找到让我们说 element 3。它需要5 steps找到它。

我的任务是创建一个名为的新函数sortedSequentialSearch()，该函数以升序接收排序列表并对其进行改进以减少查找 element 所需的步骤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()？

标签： pythonsequential

Answer 1

You can use binary search after sorting the array. It has log(n) time complexity.

In this case 2.3 steps, which is better than 3.

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