Tìm cặp gần nhất từ hai mảng đã sắp xếp trong C++

Cho hai mảng đã sắp xếp A1[m], A2[n] và số x. Tìm cặp (A1[i], A2[j]) sao cho |A1[i] + A2[j] - x| nhỏ nhất.

Thuật toán hai con trỏ (Two Pointers) - O(m+n)

1. Khởi tạo left = 0 (đầu A1), right = n-1 (cuối A2).
2. Khi left < m && right >= 0:
   • Tính sum = A1[left] + A2[right].
   • Cập nhật cặp tốt nhất nếu |sum - x| nhỏ hơn.
   • Nếu sum > x → giảm right (giảm tổng).
   • Nếu sum < x → tăng left (tăng tổng).

Ví dụ minh họa (C++)

#include <iostream>
#include <cmath>
#include <climits>
using namespace std;

void findClosestPair(int A1[], int A2[], int m, int n, int x) {
    int diff = INT_MAX;
    int left_res = 0, right_res = 0;
    int left = 0, right = n - 1;
    while (left < m && right >= 0) {
        int sum = A1[left] + A2[right];
        if (abs(sum - x) < diff) {
            diff = abs(sum - x);
            left_res = left;
            right_res = right;
        }
        if (sum > x) --right;
        else ++left;
    }
    cout << "Cap gan nhat: [" << A1[left_res] << ", " << A2[right_res] << "]\n";
}

int main() {
    int ar1[] = {1, 4, 5, 7};
    int ar2[] = {10, 20, 30, 40};
    int m = sizeof(ar1)/sizeof(ar1[0]);
    int n = sizeof(ar2)/sizeof(ar2[0]);
    int x = 32;
    findClosestPair(ar1, ar2, m, n, x);
    return 0;
}

Kết quả

Cap gan nhat: [1, 30]