CODEWITHSUNDEEP
pythonalgorithmbinary-search
cliff_leaf
cliff_leaf

Reputation: 137

Python - Binary search being too slow and crashes computer - how can I improve the algorithm

I have been working on a binary search problem.

Instead of matching one key number to a given list, the problem required me to match a list (list B) of keys to another list (list A). If a key matches a number in list A, then the output should return the first index in A where the number is present. If the key number is not present in list A, then return -1

Say that list A and list B are:

A = [1, 5, 8, 12, 13]
B = [8, 1, 23, 1, 11]

Since 8 is present in both list, the output is 2 because 8 in list A is at [2]. Using this logic, the overall final output should become:

matched_list = [2, 0, -1, 0, -1]

Below is my code. It would be much appreciated if you could also find any logic errors within in lines, however, my biggest concern is the run time. When I press enter on my computer, it took ages to process, and the software (I used VS Code) eventually crashes.

I had 16GB RAM and Intel Core i7, so it shouldn't be the device that dragged it down, but the algorithm.

def binary_search(A, B, n):
# We match the numbers in key list, B, to the numbers in A

    low, high = 0, n-1
    # low limit is initialised to A[0], the first number of list A
    # high limit initialised to the last number of the list, A[n-1]

    matched_list = []

    for i in B:
        middle = (high+low)//2

        while low <= high:
            if i > A[middle]:
                low = middle+1 

            elif i < A[middle]:
                high = middle-1 
            
            else:
                matched_list.append(middle)
    
        if low > high:
            return(-1)

    return(matched_list)

A = [1, 5, 8, 12, 13]
B = [8, 1, 23, 1, 11]
n = 5  # this is the length of list A


print(binary_search(A, B, n))

Would there be a way to improve my algorithm?

Upvotes: 1

Views: 149

Answers (4)

Daniel Hao
Daniel Hao

Reputation: 4980

@cliff_leaf, in your case, it would be easier just to use dict() to save the number-index in dictionary for a quick O(1) lookup later by B: (Binary Search is prob. not appropriate in the case.) You could adjust the code to break/exit when you find the first matching number - 8 and stop, if that's what you want - find the first matching.

>>> A = [1, 5, 8, 12, 13]
>>> B = [8, 1, 23, 1, 11]
>>> aa = {n: i for i, n in enumerate(A)}
>>> aa
{1: 0, 5: 1, 8: 2, 12: 3, 13: 4}
>>> for n in B:
    if n in aa: print(aa[n])

    
2
0
0

Upvotes: 1

Devi Khositashvili
Devi Khositashvili

Reputation: 576

1st - you can't use binary search if space isn't sorted.

2nd - if you want better algorithm use maps and complexity will be linear

3rd - if you want to use a binary search, you can easily insert your values in set and then find the answer with lower_bound.

Upvotes: 1

Abhinav Mathur
Abhinav Mathur

Reputation: 8101

In your code,

while low <= high:
            if i > A[middle]:
                low = middle+1 

            elif i < A[middle]:
                high = middle-1 
            
            else:
                matched_list.append(middle)

The else statement doesn't break, because of which it gets stuck in an infinite loop. Adding a break statement would solve it.
Suggestion: Since maps/dictionaries tend to be faster, you can use them to effectively solve this in O(N) rather than O(NlogN).

Upvotes: 1

ibutskhrikidze
ibutskhrikidze

Reputation: 156

I fixed bugs in the function. see this code:

def binary_search(A, B, n):
    matched_list = []

    for i in B:
        low, high = 0, n - 1
        while low <= high:
            middle = (high + low) // 2
            if i > A[middle]:
                low = middle + 1
            elif i < A[middle]:
                high = middle - 1
            else:
                matched_list.append(middle)
                break

        if low > high:
            matched_list.append(-1)

    return matched_list

Upvotes: 1

Related Questions