Solve the problem using an algorithm using javascript

Question

I am working on the following example

Given: 2 sorted arrays of integers(e.g. A = [1,2,3,4,5], B = [6, 7, 8, 9, 10]) and answer(e.g 13)
Find: What I have to do is to find pair of indices(1 in each array) of those two elements in both arrays so when I add them then it should be equal to the given answer.

I used the following 2 solutions. But the problem with both of them is that I iterate over both arrays. First I go through the first array and inside this loop I through the second array. And add items at these two indexes to see if adding them matches the answer. It works fine and outputs the correct answer. The problem is submission. If we have 10,000 integers in both arrays, then these loops will require a lot of resources, such as time, processor and memory, that will be executed and get an answer.

How can I solve a more specific problem in a more efficient way?

function find (A1, A2, ans) {
  var a = [];
  for (var i = 0, len1 = A1.length; i < len1; i++) {
    for (var j = 0, len2 = A2.length; j < len2; j++) {
      if (ans === A1[i] + A2[j]) {
        a.push(i + ', ' + j);
      }
    }
  }
  return a;
}

second

function search (A, B, ans) {
  var arr = [];
  A.map(function (v, i) {
    B.filter(function (val, ind) {
      if (ans === v + val) arr.push(i + ', ' +ind);
    });
  });
  return arr;
}

Answer 1

Solution1
(answer - array[index]), O(N log M).

++

Solution2
, . mapA mapB N+M, mapA [i] A, ^th -1 . mapB.

/* Merge the arrays */
mapA, mapB, MA all are arrays of size M+N, initialized with all -1
i = 0, j = 0
while(i < M && j < N)
    if(A[i] < B[j])
        MA[i+j] = A[i];
        mapA[i+j] = i++;
    else
        MA[i+j] = B[j];
        mapB[i+j] = j++;
while(i < M)
    MA[i+j] = A[i];
    mapA[i+j] = i++;
while(j < N)
    MA[i+j] = B[j];
    mapB[i+j] = j++;

/* Search the pair */
i = 0
j = N + M - 1
while(i < j){
   if(mapA[i] == -1) i++;
   else if(mapB[j] == -1) j--;
   else if (MA[i] + MA[j] == answer) return pair(mapA[i], mapB[j]);
   else if (MA[i] + MA[j] <  answer) i++;
   else if (MA[i] + MA[j] >  answer) j--;
}
return null_pair;  // no answer found

++

Solution3
( ), , O (N + M) .

i = 0
j = M - 1
while(i < N && j >= 0){
   if      (A[i] + B[j] == answer) return pair(i, j);
   else if (A[i] + B[j] <  answer) i++;
   else if (A[i] + B[j] >  answer) j--;
}
return null_pair;  // no answer found

Proof
, A[x] + B[y] = answer. x i, j y, , , A[i] + B[j] = answer. , , x i. j > y, A[i] + B[j] > answer, j . , .

Answer 2

// get all pairs of number from array a and b, that a[i] + b[j] = sum
// return array of pairs
function getSumPairs(a, b, sum) {
    var pa = 0, pb = b.length - 1;
    var pairs = [];
    while (pa < a.length && pb >= 0) {
        if (a[pa] + b[pb] > sum ) {
            pb = pb - 1;
        } else if (a[pa] + b[pb] < sum) {
            pa = pa + 1;
        } else {
            pairs.push([a[pa], b[pb]]);
            pa = pa + 1;
            pb = pb - 1;
        }
    }
    return pairs;
}


// data for test
var arr1 = [-1, 1, 2, 3, 4, 5, 7, 9],
    arr2 = [5, 7, 10, 12, 13, 14, 15];

console.log(getSumPairs(arr1, arr2, 14))
console.log(getSumPairs(arr1, arr2, 15))

a b . :

a[i] + b[j] < sum, a[i] + b[j-1] - sum, i.

if a[i] + b[j] > sum, a[i+1] + b[j] - , sum, j.

, . O(M + N), a [N] b [M].

http://jsfiddle.net/9L4p1j3L/

Answer 3

function find (A1, A2, ans) {
  var a = [];
  for (var i = 0, len1 = A1.length; i < len1; i++) {
    var noToSearch = ans - A1[i];
    var secondIndex  = binarySearch(A2,noToSearch);
    if(secondIndex !=-1){
        a.push(i + ', ' + secondIndex );
    }
  }
  return a;
}

function binarySearch(A2,num){
 var index = -1;
  //write binary search algo to find the element in array A2
 return index;
}