Pythonで欠落している数値を見つける方法｜二分探索による効率的な解法

問題の概要

0からnまでの連続する整数で構成されたリストがあり、そのうち1つの数値だけが欠落しているとします。このとき、欠けている数値をできるだけ効率的に求めることが課題となります。

例えば、A = [0, 1, 2, 3, 4, 5, 7, 8, 9] というリストの場合、欠落している数値は 6 です。

二分探索を使った解法

この問題は、二分探索（バイナリサーチ）のアプローチを用いることで、O(log n) の時間計算量で効率的に解くことができます。

アルゴリズムの手順

1. リストを昇順にソートする
2. high をリストAの長さ、low を 0 として初期化する
3. low < high である間、以下の処理を繰り返す
   • mid = low + (high - low) / 2 を計算する
   • A[mid] > mid であれば、high = mid とする（欠落位置は左側にある）
   • そうでなければ、low = mid + 1 とする（欠落位置は右側にある）
4. ループ終了後、low の値を返す

実装例

以下は、上記のアルゴリズムをPythonで実装したコードです。

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        high = len(nums)
        low = 0
        while low<high:
            mid = low + (high-low)//2
            if nums[mid]>mid:
                high = mid
            else:
                low = mid+1
        return low
ob1 = Solution()
print(ob1.missingNumber([5,3,1,7,8,0,9,2,4]))

入力

nums = [5,3,1,7,8,0,9,2,4]

出力

6

コードの解説

ソート後のリストでは、欠落位置より前の要素は「インデックスと値が一致」し、欠落位置以降の要素は「値がインデックスよりも大きく」なります。二分探索によって、この境界となる最初の位置を絞り込んでいくことで、欠落している数値を正確に特定できます。

この手法は、全要素を線形に走査する O(n) のアプローチと比べ、計算量を O(log n) に抑えられるため、大規模なデータセットでも高速に動作するのが大きな利点です。