intersection of 2 lists without using the in operator or any built-in functions

Does anyone know how i can use a merging algorithm that is efficient and reduces the number of comparison to a minimum?

I thought about an skip pointer but i don’t know how to implement it

my code right now:

a = [18, 23, 53, 69, 77, 91, 102, 116, 135, 159, 160, 161, 162, 163, 164, 165, 166]
b = [7, 120, 138, 159, 160, 161, 162, 163, 164, 165, 166]

i, j = 0, 0
intersection = []
while i < len(a) and j < len(b):
    if a[i] == b[j]:
        intersection.append(a[i])
        i += 1
        j += 1
    elif a[i] > b[j]:
        j += 1
    else:
        i += 1
        
print(intersection)

Does this do what you need?

a = [18, 23, 53, 69, 77, 91, 102, 116, 135, 159, 160, 161, 162, 163, 164, 165, 166]
b = [7, 120, 138, 159, 160, 161, 162, 163, 164, 165, 166]
c = [*a, *b]

That would be the concatenation of the two lists, not intersection, and it could be written more cleanly as a + b.

1 Like

Yes, true – I need to sleep; insomnia is a double-edged sword.

1 Like

Why not use sets and the intersection operator (which is an operator, not a function, builtin or otherwise)? A set is a far more appropriate and efficient data structure for this problem…lists are for things that have order and contain multiple identical, potentially non-hashable elements, none of which are desirable here.

intersection = set(a) & set(b)
2 Likes

Hello, @Willien, and welcome to Python Software Foundation Discourse!

So that we are able to provide good advice, we need to know exactly what you are trying to do.

Are you trying to merge the lists, with duplicates and ordering preserved? Alternatively, are you trying to find the intersection of two lists, without duplication of the items that occur in both lists?

This does suggest that you intend to avoid duplication:

    if a[i] == b[j]:
        intersection.append(a[i])
        i += 1
        j += 1

Thanks for the answers