One Pointer Search vs Two Pointer Search

Question

Which algorithm is better in terms of time complexity and space complexity ?

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
    # two pointer algorithm to find the element in array
    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)

i am expecting two pointer search algorithm to perform better on large list.

Answer 1

Both algorithms have space complexity O(1) and time complexity O(n) where n is the size of the list. The two-pointer version just checks the elements in a different order. If the value you are looking for is near the end of the list, it will find it faster because it checks those earlier than the simple version. But if the value is near the start or middle of the list, it will be slower, because it's doing checks on later elements that the simple algorithm wouldn't get to.

Imagine you have a list [A,B,C,D,E,F] and you are looking for the value D. The simple algorithm checks A,B,C,D and then finishes. The two-pointer version checks A,F,B,E,C,D and then finishes. It's only faster if you're looking for E or F.

Overall, it's not faster unless you have reason to think that the value you are looking for is likely to be near the end of the list.