Faster way to extract close pairs from two arrays?

You might do in O(N log N) (+ number of resulting pairs (which might exceed N log N)):

std::sort(std::begin(A), std::end(A)); // O(N log N)
std::sort(std::begin(B), std::end(B)); // O(N log N)

auto begin = std::begin(B);
auto end = begin;
for (auto v : A) {
    while (begin != std::end(B) && *begin < v - 50) ++begin;
    while (end != std::end(B) && *end < v + 50) ++end;
    for (auto it = begin; it != end; ++it) {
        std::cout << '(' << v << ", " << *it << ")\n";
    }
}

Demo

Try a) binary searching the second array b) remembering previous positions in the second array and c) tracking the distance between elements in the first array. The first step is log(n) instead of n, and the second step makes the search space smaller for later searches. The third step reuses previous distance calculations.

For example, binary search for items with max distance 50 from 432, giving you the lowest and highest indexes, 3 and 6. For the next element, 615, you can ignore items below the lowest index 3. That's a) and b). See https://en.wikipedia.org/wiki/Binary_search_algorithm#Procedure_for_finding_the_leftmost_element

For many arrays, you can save calculations by storing the max distance values of previous searches. For 427 you would store 394 and 473, their index and distance values, i.e. (3,-33) and (6,46). Suppose the next item was 430. Now, instead of doing the binary search, you can just check the distance with the previous element, abs(430-427), and subtract it from the stored distances, giving you -36 and 43. You can then conclude 430 has a superset of the distance set of 427 without searching those elements. Suppose the next value is 615. This gives you abs(615-427) or 188, so you get -221 and -142. Both are too large, so you can skip all of them, starting the binary search of a) with index 7 (6+1), instead of 3.

NB edit: OP is no longer the same, the arrays were sorted and had different values.

Building off of Jarod42's answer, I tried to distill everything down to standard algorithms and containers and was able to get something like this

#include <set>

void print_close_pairs(vector<int> const& A, vector<int> const & B){
    auto a = std::multiset<int>(A.cbegin(),A.cend()); // O(n * log(n))
    auto b = std::multiset<int>(B.cbegin(),B.cend()); // O(m * log(m))

    for (auto v: a){ // O(n)
        auto beg = b.lower_bound(v - 50); // O(log(m))
        auto end = b.upper_bound(v + 50); // O(log(m))
        for (; beg != end; beg++) { // O(m)
            std::cout << '(' << v << ", " << *beg << ")\n";
        }
    }
}

We see that A and B need to be treated as separate complexity variables n and m respectively. We also find that only one of the inputs needs to be put into a set (or sorted). So while we can't escape O(n * m) complexity, we are still doing a lot of extra work.

void mark_pairs(vector<int> const& A, vector<int> const & B){
    auto b = std::multiset<int>(B.cbegin(),B.cend()); // O(m * log(m))

    for (auto v: A){ // O(n)
        auto beg = b.lower_bound(v - 50); // O(log(m))
        auto end = b.upper_bound(v + 50); // O(log(m))
        for (; beg != end; beg++) { // O(m)
            std::cout << '(' << v << ", " << *beg << ")\n";
        }
    }
}

Beyond that, there are few more things that you could do to massage the data to only work on the smallest subsets, but I think you're really limited to a O(n*m) complexity.

Side note: beware of only sorting, because you could accidentally hit worst case time complexity of O(n² + m²) complexity

I suggest to exploit the fact that there is no space cost and the fact that we deal with integers, and use it to find an algorithm in time O(n) or as Alex defined each array length with different variable (and I completely agree) O(n+m).

1. Go over the first array (call it A - length=n) and define a new array where each cell points to a linked list, the linked list will contain all relevant items from A. for every element a, add its number to linked lists at locations [a-50:a+50]. This construction is O(n)
2. Go over each element in the second array (call it B - length =m), for each element b the relevant items from A are in cell b. Time complexity O(m)