Pythonで解く「最初の不良バージョン」問題：二分探索による効率的なアプローチ

問題の概要

ある会社で、プロダクトマネージャーが新しい製品を開発するチームを率いているとします。最新バージョンが品質チェックに不合格となった場合、各バージョンは前のバージョンをベースに開発されているため、不良バージョン以降のすべてのバージョンも不良になると仮定できます。

そこで、n個の要素を持つ配列 A = [1, 2, …, n] が与えられたとき、この中から最初の不良バージョンを見つける必要があります。

ここでは、指定されたバージョンが不良かどうかを判定する関数 isBadVersion(version_id) が用意されているものとします。例えば、n = 5 でバージョン4が最初の不良バージョンである場合、isBadVersion(3) は False を返し、isBadVersion(4) と isBadVersion(5) は True を返します。このとき、最初の不良バージョンは 4 です。

解法のアプローチ

この問題を解くには、以下の手順に従います。

• n < 2 の場合は、そのまま n を返す
• isBadVersion 関数を活用し、二分探索（バイナリサーチ）によって不良バージョンを検出する

先頭から順に調べる線形探索では O(n) の計算量が必要ですが、二分探索を使えば O(log n) で効率的に最初の不良バージョンを特定できます。

実装例

以下の実装例を見て、理解を深めましょう。

first_bad = 0

def isBadVersion(version):
    if version >= first_bad:
        return True
    return False

class Solution:
    def firstBadVersion(self, n):
        if n < 2:
            return n
        start = 1
        end = n
        while(start <= end):
            mid = (start + end) // 2
            if isBadVersion(mid) and not isBadVersion(mid - 1):
                return mid
            elif isBadVersion(mid - 1):
                end = mid - 1
            else:
                start = mid + 1

ob1 = Solution()
first_bad = 4
op = ob1.firstBadVersion(5)
print(op)

入力

5
4

出力

4

コードの解説

このアルゴリズムの動作を順を追って説明します。

• 初期化： 探索範囲の始点 start を 1、終点 end を n に設定します。
• 二分探索： start が end 以下である間、中央の値 mid を計算します。
• 境界の判定： mid が不良バージョンであり、かつ mid - 1 が正常なバージョンであれば、mid こそが最初の不良バージョンなので即座に返します。
• 範囲の絞り込み： mid - 1 も不良バージョンであれば、答えは左側にあるため end を mid - 1 に更新します。そうでなければ答えは右側にあるため、start を mid + 1 に更新します。

このように、ループごとに探索範囲を半分に絞り込むことで、O(log n) の時間計算量で最初の不良バージョンを効率的に見つけられるのが、この手法の大きな強みです。