Find the closest pair from two sorted arrays in Python

In this tutorial, we will learn how to find the closest pair from two sorted arrays in Python with an example.

Explaination

In this problem we are given two sorted arrays and a number m and we have to find the pair whose sum is closest to x and the pair has an element from each array.We are given two arrays array1[0…g-1] and array2[0..h-1] and a number m, we need to find the pair array1[i] + array2[j] such that absolute value of (array1[i] + array2[j] – x) is minimum.

A Simple Solution is to run two loops. The outer loop considers every element of first array and inner loop checks for the pair in second array. We keep track of the minimum difference between array1[i] + array2[j] and m. Merge given two arrays into an auxiliary array of size m+n using merge sort. While merging keep another boolean array of size g+h to indicate whether the current element in merged array is from array1[] or array2[]. Consider the merged array and use the find the pair with sum closest to x. One extra thing we need to consider only those pairs which have one element from array1[] and other from array2[], we use the boolean array for this purpose.

Below is our required Python code that shows how to find the closest pair from two sorted arrays:

import sys

def printClosest(array1, array2, g, h, m):

difference=sys.maxsize

l = 0
v = h-1
while(l < h and v >= 0):

if abs(array1[l] + array2[v] - m) < difference:
res_l = l
res_v = v
difference = abs(array1[l] + array2[v] - m)

if array1[l] + array2[v] > m:
v=v-1
else:
l=l+1
print("The closest pair is [", array1[res_l],",",array2[res_v],"]")

array1 = [6, 40, 50, 70]
array2 = [15, 22, 35, 45]
g = len(array1)
h = len(array2)
m = 38
printClosest(array1, array2, g, h, m)

Below is the given output for our program:

The closest pair is[6,35]