Pythonで等差数列から欠落した項を見つけるプログラム

配列 nums には、ある等差数列の n−1 個の項が格納されているとします。この配列では、先頭または末尾以外の要素が1つだけ事前に削除されています。ここでの課題は、その削除された数値を見つけることです。

たとえば、入力が nums = [5, 7, 11, 13] の場合、出力は 9 になります。これは、各項が「2i+5」という式に従っており、i = 2 のとき 2×2 + 5 = 9 となる項が欠落しているためです。

解決のためのアプローチ

この問題は、二分探索（バイナリサーチ）の考え方を応用することで効率的に解けます。等差数列では各項が「初項 ＋ 公差 × インデックス」で表せるため、期待される値と実際の値が食い違う位置を絞り込んでいくのがポイントです。手順は以下の通りです。

• nums のサイズが 2 の場合 → 全要素の合計を 2 で割った値（小数点以下切り捨て）を返す
• nums[0] と nums[1] が等しい場合 → nums[0] を返す
• lower := nums[0]（初項）
• upper := nums の末尾の要素
• interval := (upper − lower) を nums のサイズで割った値の小数点以下切り捨て（公差）
• pointer := nums のサイズを 2 で割った値の小数点以下切り捨て
• left := 0、right := nums のサイズ − 1
• left と right が一致しない間、以下を繰り返す：
  • nums[pointer] が nums[0] ＋ interval × pointer と異なる場合：
    • nums[pointer − 1] が nums[0] ＋ interval × (pointer − 1) と等しければ、nums[0] ＋ interval × pointer を返す
    • そうでなければ、right := pointer とし、pointer := (left ＋ right) ÷ 2 の小数点以下切り捨て
  • それ以外の場合：
    • right − left が 1 なら、pointer := right
    • そうでなければ、left := pointer とし、pointer := (left ＋ right) ÷ 2 の小数点以下切り捨て

実装例

理解を深めるために、以下の Python 実装例を見てみましょう。

def solve(nums):
    if len(nums) == 2:
        return sum(nums) // 2

    if nums[0] == nums[1]:
        return nums[0]

    lower = nums[0]
    upper = nums[-1]
    interval = (upper - lower) // len(nums)

    pointer = len(nums) // 2

    left = 0
    right = len(nums) - 1

    while left != right:
        if nums[pointer] != nums[0] + interval * pointer:
            if nums[pointer - 1] == nums[0] + interval * (pointer - 1):
                return nums[0] + interval * pointer
            else:
                right = pointer
                pointer = (left + right) // 2
        else:
            if right - left == 1:
                pointer = right
            else:
                left = pointer
                pointer = (left + right) // 2

nums = [5, 7, 11, 13]
print(solve(nums))

入力

[5, 7, 11, 13]

出力

9

まとめ

このアルゴリズムは、等差数列の性質（各項が「初項 ＋ 公差 × インデックス」で表せること）を利用し、二分探索によって欠落した項を特定します。探索範囲を半分ずつ狭めていくため、計算量は O(log n) となり、全要素を順番に調べる線形探索（O(n)）よりも大幅に高速に動作するのが特徴です。