Binary search to insert a value to a sorted list

Question

I'm trying to insert values from list B in to list A.

List A is always sorted in descending order and can get quite big (2x10^5).

List B is always sorted in ascending order and can also be of the size 2x10^5

I want to insert the values from B to A whilst still having the descending order. I used binary search to find the index positions of where I should add the value.

However for this one test case I am having a peculiar bug that I can't seem to fix

def binarySearch(arr, low, high, x):
    while low < high:
        mid = low + (high - low) // 2;
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            high = mid - 1
        else:
            low = mid + 1
    if low >= high:
        return(low)

for i in B:
    indexpos = binarySearch(A, 0, len(A)-1, i)
    if indexpos == 0:
        A = [i] + A
    else:
        A = A[:indexpos+1] + [i] + A[indexpos+1:]
    print(A)

Here is a sample input that works:

A = [100,100,50,40,40,20,10]
B = [5,25,50,120]

Output: A = [120, 100, 100, 50, 50, 40, 40, 25, 20, 10, 5]

I can't figure out why this one doesn't work:

A = [100,90,90,80,75,60]
B = [50,65,77,90,102]

Output: A = [102, 100, 90, 90, 90, 80, 75, 77, 65, 60, 50]

Any help would be much appreciated

Answer 1

Your while loop should continue while low <= high, and you should return high. Only this way you ensure that the returned index has a value that is not greater than x.

In the main code you should not have a special case for indexpos == 0

So:

def binarySearch(arr, low, high, x):
    while low <= high:
        mid = low + (high - low) // 2;
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            high = mid - 1
        else:
            low = mid + 1
    return high

for i in B:
    indexpos = binarySearch(A, 0, len(A)-1, i)
    A = A[:indexpos+1] + [i] + A[indexpos+1:]

print(A)

Note that since you read all values in A, each time you make an assignment to A, the benefit of binary search is zero: one assignment to A costs O(n), where n is the size of A, while the first binary search "only" costs O(logn). The bottle neck is thus the assignment to A. The time complexity of this algorithm is O(nm), where n and m are the sizes of both lists.

You should just allocate the necessary extra space for A only once, and then move elements from A (starting from the last real value in A) to the end of the now extended list, while comparing with values from B (starting from left to right): either put the value from A or B there, and work your way through both lists like that.

This will make the process O(n+m).

Here is an implementation of that idea:

m = len(A)
n = len(B)
k = m + n

# extend A only once
A.extend([0] * n)

# move values to the extended area
m -= 1
for b in B:
    k -= 1
    while m >= 0 and A[m] < b:
        A[k] = A[m]
        k -= 1
        m -= 1
    A[k] = b

print(A)

Answer 2

To improve your code, look at trincot's answer; but as he also said, be aware that using a binary search for each element of B is probably not the most efficient method here.

trincot provides a better algorithm and if you want a more pythonic solution you can have a look here: Combining two sorted lists in Python