单指针搜索与双指针搜索：时间与空间复杂度对比问询

实现代码 #

temp_list = [2,4,1,3,7,1,4,2,9,5,6,8]
def get_item_from_list1(collection, target):
    collection_length: int = len(collection)
    if collection_length == 0:
        return None
    # 双指针查找元素
    left_index: int = 0
    right_index: int = collection_length - 1
    while left_index <= right_index:
        if collection[left_index] == target:
            return collection[left_index]
        if collection[right_index] == target:
            return collection[right_index]
        left_index += 1
        right_index -= 1
    return None


def get_item_from_list2(collection, target):
    for item in collection:
        if item == target:
            return item
    return None


get_item_from_list1(temp_list, 9)
get_item_from_list2(temp_list, 9)

时间复杂度对比 #

• 双指针搜索（get_item_from_list1）：
  • 最优情况：目标在列表首尾，仅1次比较即可找到，时间复杂度为O(1)。
  • 最坏情况：目标不存在或位于列表中间区域，需要遍历约一半元素，时间复杂度简化后为O(n)。
• 单指针搜索（get_item_from_list2）：
  • 最优情况：目标在列表首位，仅1次比较，时间复杂度O(1)。
  • 最坏情况：目标不存在或在列表末尾，需遍历全部元素，时间复杂度O(n)。

空间复杂度对比 #

两种算法的空间复杂度均为O(1)——仅使用固定数量的额外变量（如索引标记），空间开销不随输入列表大小变化。

算法优劣总结 #

从渐近时间复杂度的最坏情况看，两者表现一致，都是O(n)。但双指针的优势仅在特定场景成立：当目标元素大概率出现在列表首尾区域时，它能更快定位元素。如果目标分布随机，两者平均性能无显著差异；若目标更常出现在列表前半段，单指针搜索反而可能更高效。

用户预期双指针在大型列表上表现更好，这个结论只适用于目标集中在首尾的场景，并非所有大型列表场景都适用。

内容的提问来源于stack exchange，提问作者SYED FAISAL