Pythonで重複する配列から欠落要素を見つける方法【二分探索で効率化】

問題の概要

互いに重複関係にある2つの配列が与えられますが、そのうち片方の配列には1つだけ要素が欠けています。この欠落している要素を見つけるのが本記事の課題です。

例えば、入力が A = [2, 5, 6, 8, 10]、B = [5, 6, 8, 10] の場合、2番目の配列には「2」が含まれていないため、出力は 2 となります。

解決のアプローチ

この問題は、二分探索（バイナリサーチ）を活用することで、O(log N) の時間計算量で効率的に解くことができます。なお、この手法は両方の配列が昇順にソートされていることを前提としています。手順は以下の通りです。

1. solve() 関数を定義します。引数として A、B、N を受け取ります。

2. N が 1 の場合、A[0] を返します。

3. A[0] と B[0] が等しくない場合、A[0] を返します。

4. low := 0、high := N - 1 と初期化します。

5. low < high の間、以下を繰り返します。

   • mid := (low + high) / 2 を計算します。

   • A[mid] と B[mid] が等しい場合、low := mid とします。

   • そうでなければ、high := mid とします。

   • low が high - 1 と等しくなったら、ループを抜けます。

6. A[high] を返します。

7. メイン処理では以下を行います。

8. M := A のサイズ、N := B のサイズ とします。

9. N が M - 1 と等しい場合、solve(A, B, M) を返します。

10. M が N - 1 と等しい場合、solve(B, A, N) を返します。

11. それ以外の場合、「Not found」を返します。

実装例

理解を深めるために、以下のPythonコードをご覧ください。

def solve(A, B, N):
    if N == 1:
        return A[0]
    if A[0] != B[0]:
        return A[0]
    low = 0
    high = N - 1
    while (low < high):
        mid = (low + high) // 2
        if A[mid] == B[mid]:
            low = mid
        else:
            high = mid
        if low == high - 1:
            break
    return A[high]

def get_missing_element(A, B):
    M = len(A)
    N = len(B)
    if N == M - 1:
        return solve(A, B, M)
    elif M == N - 1:
        return solve(B, A, N)
    else:
        return "Not found"

A = [2, 5, 6, 8, 10]
B = [5, 6, 8, 10]
print(get_missing_element(A, B))

入力

[2, 5, 6, 8, 10], [5, 6, 8, 10]

出力

2

まとめ

この記事では、ソート済みの2つの配列から欠落している要素を二分探索で見つける方法を解説しました。先頭や末尾の不一致を早期に判定しつつ、中央値の比較を繰り返すことで、線形探索の O(N) に対して O(log N) まで計算量を削減できる点が大きなメリットです。大量のデータを扱う場面で特に有効なテクニックなので、ぜひ実際のコードで試してみてください。