Given the number X, find two elements in two sorted arrays, such as A [i] + B [j] = X in O (n + m)

Question

Given the following problem, I will be grateful for any corrections, since I do not have a solution for the current question (taken from one of my exams professors !!!):

Note: this is not homework!

Problem:

For two sorted arrays A (with length n ) and B (with length m ), where each

Element

(in both arrays) is a real number, and the number X (also a real number),

we would like to know whether a ∈ A and b ∈ B exist or not, for example:

a + b = X , at O(n+m) runtime.

Decision:

First, we start checking from the end of both arrays, since we do not need numbers that are larger than X :

• i = n

• k = m

• whereas A [i]> X, i = i-1

• whereas B [k]> X, k = k -1

Define j = 0. Now start with the current i in A and from j to B :

• while i > 0 , j < k :
• if A[i]+B[j] == X , then return both cells
• else j = j+1 , i = i -1

As a result, we will either have two elements, or we will go beyond the bounds of one or both arrays, which means that there are no two elements, such a + b = X

Any comments would be greatly appreciated

thanks

Answer 1

You do not have to configure i and j at the same time. If the amount is too large, you should reduce i . If it is too small, increase j .

Answer 2

This problem is a special case of the following question: Find the number in the sorted matrix (row n columns) in O (log n)

Consider a matrix filled with C[i,j] = A[i] + B[j] , then, starting from one of the angles, you decrease i if the sum is too large, and if it is too small, increase j . Of course, you do not need to create and / or populate this matrix C in your program, just assume that you know some element of this matrix: it A[i] + B[j] , you can calculate it immediately at any time. The resulting algorithm is O(m+n) .