Algorithm for searching a value in two arrays

Question

Task: A and B are arrays of natural numbers. A is an incrementally sorted array and B is randomly ordered one. K is some arbitrary natural number. Find an effective algorithm which determines all possible pairs of indexes (i,j) such that A[i]+B[j]=K.

Is this algorithm the most efficient?

public static void main(String[] args) {
            int A[] = { 1, 2, 3, 4, 6, 7, 8, 11, 13, 124};
            int B[] = {4, 1, 10, 5};
            int k = 10;
            int i = 0, n = A.length, m = B.length;
            ArrayList<String> result = new ArrayList<String>();
            while (i < n){
                if (A[i] >= k) {
                    break;
                }else {
                    int j = 0;
                    while(j < m) {
                        if (A[i] + B[j] == k) {
                            result.add("i = " + i + " j = " + j);
                        }
                        j++;
                    }
                }
                i++;
            }
            for(int z = 0; z < result.size(); z++) {
                System.out.println(result.get(z));
            }
}

Iterate numbers in B and for each b in B, binary-search for k-b in A. — tobias_k
– tobias_k, Commented Oct 20, 2017 at 14:41
"Is this algorithm the most efficient" No. You could start from the middle of your A table. Then go down or up depending of the result of A[i] + B[j]. That would be more efficient, so it can't be the most efficient. EDIT: Actually that's what @tobias_k is proposing — Turtle
– Turtle, Commented Oct 20, 2017 at 14:43

tobias_k · Accepted Answer · 2017-10-20 14:46:01Z

6

No, the algorithm is not very efficient. While you break as soon as you find an a in A which is greater than k, you still have to test all combinations of a and b before that, giving your algorithm a complexity of O(m n), with n being the number of elements if A and m the number of elements in B.

Instead, I'd suggest the following:

loop over all the elements b in B
determine a = K - b
use binary search to find the index of a in A, if it exists
if a exists in A, print the indices of a and b

This makes use of the fact that since A is sorted, we can quickly determine whether for a given b, an a such that a + b = k exists in A. The reverse is not possible, as B is randomly ordered. The total complexity for this is O(m log n).

answered Oct 20, 2017 at 14:46

tobias_k

83.1k12 gold badges130 silver badges186 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

tobias_k Over a year ago

Some more optimizations: First, binary-search for k in A and then use that index as the upper-bound for all the other binary-searches, and if b > k, don't search at all.

DAle Over a year ago

This answer is correct only if there are no duplicates in A.

tobias_k Over a year ago

@DAle That's a very good point. You can still use the binary search, but from the index found, you'd also have to check and print the previous and next indices until you find a different a.

fjardon Over a year ago

In the worst case, A and B contains single values a and b such that a+b=K. Printing all the matching pairs of indexes will take at least (n*m) operation. So no algorithm can go under O(n*m).

tobias_k Over a year ago

@fjardon Yes, in the extreme case that there are in fact n * m solutions, the algorithm will take n * m time, but in the general case, where there are none or few duplicates, the complexity should still be O(mlogn).

Collectives™ on Stack Overflow

Algorithm for searching a value in two arrays

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related