My implementation of binary search through two lists is exhorbitantly slow

Question

For an algorithms class I'm in, we are implementing some algorithms and testing their speed. I chose Python as my language to do this. We are given 2 unsorted lists and a number x, and we want to find if there are any elements a in S1 and b in S2 such that a + b = x. The way I did it is this:

def find_in(s, s2):
    start, end = 0, len(s2)-1
    while end >= start:
        mid = start + (end - start) // 2
        if s2[mid] == s:
            return True
        if s2[mid] > s:
            start = mid +1
        if s2[mid] < s:
            end = mid - 1
    return False

@timing
def binary_search(x, s1 : list, s2 : list) -> bool:
    return any( find_in(x - s, sorted(s2)) for s in s1 )

So the function loops through an unsorted list and then looks for the element x - s in the sorted list using binary search. For whatever reason, for a list length of 10000 generated using Python random module, it is taking 10 seconds on average, which is longer than the brute force method I tried. Is there some subtly in what I wrote that I am missing? I feel as though this should be O(n log n), faster than O(n²)

Answer 1

Logic:

• given a+b = x
• this implies b = x-a (we know x, we know a, we need to find if b exists or not).
• this implies a = x-b (we know x, we know b, we need to find if a exists or not). {this part is not required i guess}

Code:

 def AplusB(arr1 , arr2, x):
        #stores the frequency of arr1 (not required i guess)
        d1 = {}
        for i in arr1:
            if(i in d1):
                d1[i] += 1
            else:
                d1[i] = 1
        #stores the frequency of arr2
        d2 = {}
        for i in arr2:
            if(i in d2):
                d2[i] += 1
            else:
                d2[i] = 1
        isAnsExists = False
        for i in arr1:
            val = x - i
            if(val in d2):
                isAnsExists = True
        for i in arr2:
            val = x - i
            if(val in d1):
                isAnsExists = True
        return isAnsExists
    

Random Tests:

x = random.randint(0, 10000)
arr1 = [random.randint(0, 100000) for i in range(100000)]
arr2 = [random.randint(0, 100000) for i in range(100000)]
print( AplusB( arr1,arr2 , x))