Pythonで連続する番号のソート済み配列から欠落した要素を見つける方法

問題の概要

n個の重複しない数値からなる配列Aを考えます。これらの要素は昇順に並んでいますが、そのうち1つだけが欠落しています。この欠落している要素を効率的に見つけ出すのが課題です。

例えば、入力が A = [1, 2, 3, 4, 5, 6, 7, 9] のような場合、出力は 8 となります。

解決の手順(アルゴリズム)

配列がソート済みであるという特性を活かし、二分探索を用いることでこの問題を解決できます。連続した数列では、欠落が発生していない位置のインデックスiに対して「A[i] − i == A[0]」という関係が常に成り立ちます。この性質を利用して、欠落位置を絞り込んでいきます。

具体的なステップ

• n := 配列Aのサイズとする
• left := 0、right := n − 1、mid := 0 で初期化する
• right > left の間、以下の処理を繰り返す
  • mid := left + (right − left) // 2 を計算する
  • もし A[mid] − mid が A[0] と等しい場合(左側に欠落がない状態)
    • A[mid + 1] − A[mid] > 1 であれば、A[mid] + 1 を返す(ここが欠落箇所)
    • そうでなければ、left := mid + 1 として右半分を探索する
  • 等しくない場合(左側に欠落が存在する状態)
    • A[mid] − A[mid − 1] > 1 であれば、A[mid] − 1 を返す(ここが欠落箇所)
    • そうでなければ、right := mid − 1 として左半分を探索する
• ループ終了後も見つからなければ、−1 を返す

Pythonでの実装例

以下のコードで実際の動作を確認してみましょう。

def search_missing_item(A):
    n = len(A)
    left, right = 0, n - 1
    mid = 0
    while (right > left):
        mid = left + (right - left) // 2
        if (A[mid] - mid == A[0]):
            if (A[mid + 1] - A[mid] > 1):
                return A[mid] + 1
            else:
                left = mid + 1
        else:
            if (A[mid] - A[mid - 1] > 1):
                return A[mid] - 1
            else:
                right = mid - 1
    return -1

A = [1, 2, 3, 4, 5, 6, 7, 9]
print(search_missing_item(A))

入力

[1, 2, 3, 4, 5, 6, 7, 9]

出力

8

計算量のポイント

このアルゴリズムは二分探索を採用しているため、時間計算量はO(log n)、空間計算量はO(1)となります。先頭から順に全要素を比較する線形探索(O(n))と比べ、大規模な配列でも大幅に高速に動作するのが大きな利点です。ソート済み配列という前提条件があるからこそ実現できる、非常に効率的なアプローチと言えるでしょう。