How to quickly find first multiple of 2 of list element in list of large integers?

Question

I have a list of approximately 100 000 sorted even integers in the range 10^12 to 10^14. My goal is to find the first integer x in the list such that x*2 is also a member of the list. As my list is rather long speed is very important.

My first thought was to just iterate over the list and check whether each element when multiplied by 2 was also in the list, but upon implementing this it is clear this is too slow for my purposes.

My next thought was to decompose each element in the list into its prime decomposition with SymPy's factorint, and then search my decomposed list for the same decomposition except with an extra 2. This didn't turn out to be any quicker obviously, but I feel like there must be a way using prime decomposition, if not something else.

Answer 1

You can iterate on your list with two iterators: one pointing to the current element and one pointing to the first one greater or equal to it's double. This will be O(N).

Here is a draft of the idea:

l = [1, 3, 5, 7, 10, 12, 15]

# ...
j = 0
for i in range(0, len(l)):
    while l[j] < 2*l[i]:
        j += 1
        if j == len(l):
            return -1
    if l[j] == 2*l[i]:
        return i

Edit: Following comments in another answer, a few performances tests show that this version will be much faster (3 times in my tests) by eliminating multiplications, calls to len and reducing number of item retrievals in the list:

j = 0
s = len(l)
for i in range(0, s):
    l_i = l[i]
    l_i2 = l_i<<1
    while l[j] < l_i2:
        j += 1
        if j == s:
            return -1
    if l[j] == l_i2:
        return i