Pythonで2つのソート済み配列から最も近いペアを見つける方法

この記事では、昇順にソートされた2つの配列から「目標値に最も近い合計を持つペア」を見つける問題と、その効率的な解法について詳しく解説します。

問題文

問題: ソート済みの2つの配列と目標値 x が与えられます。各配列から1つずつ要素を選んで作るペアのうち、その合計が x に最も近くなる組み合わせを見つけてください。

解き方のポイント:二ポインタ法

すべてのペアを総当たりで調べると計算量は O(m×n) になりますが、配列がソート済みであることを活かせば、二ポインタ法によって O(m+n) まで高速化できます。手順は以下の通りです。

• 片方の配列は先頭から、もう片方の配列は末尾から走査を開始します。
• 現在のペアの合計が x より大きい場合は、大きい側のポインタを左へ動かして合計を減らします。
• 合計が x 以下の場合は、小さい側のポインタを右へ動かして合計を増やします。
• 各ステップで「合計と x の差の絶対値」を確認し、最小となったペアを記録しておきます。

実装例(Pythonコード)

# sysモジュール
import sys

# 最も近いペアを見つける関数
def find_closest_pair(ar1, ar2, m, n, x):
    # 差の最小値(初期値はシステム最大値)
    diff = sys.maxsize
    # ポインタの初期化
    l = 0
    r = n - 1
    while l < m and r >= 0:
        # 現在のペアがこれまでより x に近ければ記録
        if abs(ar1[l] + ar2[r] - x) < diff:
            res_l = l
            res_r = r
            diff = abs(ar1[l] + ar2[r] - x)
        # ペアの合計が x より大きければ右側ポインタを左へ
        if ar1[l] + ar2[r] > x:
            r -= 1
        # そうでなければ左側ポインタを右へ
        else:
            l += 1
    # 結果を表示
    print("最も近いペアは [", ar1[res_l], ",", ar2[res_r], "]")

# メイン処理
ar1 = [1, 3, 6, 9]
ar2 = [11, 23, 35, 50]
m = len(ar1)
n = len(ar2)
x = 20
find_closest_pair(ar1, ar2, m, n, x)

出力結果

最も近いペアは [ 9 , 11 ]

上記の実行例では、ar1 = [1, 3, 6, 9]、ar2 = [11, 23, 35, 50]、目標値 x = 20 としています。9 + 11 = 20 となり差が 0 になるため、[9, 11] が最も近いペアとして出力されます。使用している変数はすべてローカルスコープで宣言されており、その役割は次の通りです。

• diff: 目標値との差の最小値(sys.maxsize で初期化)
• l / r: ar1 の先頭・ar2 の末尾を指す2つのポインタ
• res_l / res_r: 最良のペアとなったインデックスを記録

計算量

• 時間計算量: O(m + n) — 各ポインタは最大でも配列の長さ分しか移動しないため
• 空間計算量: O(1) — 追加のデータ構造が不要

まとめ

この記事では、二ポインタ法を用いて、2つのソート済み配列から目標値に最も近いペアを効率よく求めるPythonプログラムを紹介しました。「配列がソート済み」という前提条件を活かすことで、総当たり法よりも大幅に高速に解ける点が大きなポイントです。