# LeetCode Easy 278. First Bad Version

tags: leetcode

問題

• Explore
• Problems

あなたはプロダクトマネジャーで現在新しい製品を開発するようにチームを指揮している.

不幸なことにあなたの製品の最新版が品質管理に落ちてしまった. それぞれのバージョンはその前のバージョンに基づいて開発されているので, 悪いバージョンの後のバージョンも全て悪い.

[1, 2, ..., n]の$n$バージョンを持っているとか停止, その後の全てものを悪くした原因の最初の悪いバージョンを見つけたい.

あなたはisBadVersion(version)というversionが悪いかどうかを返すブールAPIを与えられている. 最初の悪いバージョンを探す関数を実装せよ. APIの呼び出しの数を最小化せよ.

アイデア

単調性があるので二分探索が使えそうです. この際に注意するのはこの問題でのバージョンは1から始める1-indexedであるという点です

解法

• もちろんn == 0ならば-1を返します
• 探索するバージョンの範囲の始端を1, 終端をnとします
  • 真ん中のバージョンをmidとします
• midが悪いものならば, midを含めたそれ以前のバージョンが最初の悪いバージョンである可能性が有ります
• そうでないならば, midを除くそれ以降のバージョンが最初の悪いバージョンである可能性が有ります
• このようにしてstart == endとなるまで続けます
• そして, このstartを返します

計算量

• 時間計算量
  • $O(\log n)$
• 空間計算量
  • $O(n)$

C++

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
  int firstBadVersion(int n) {
    if (n == 0) return -1;
    
    int start = 1, end = n;
    while (start < end) {
      int mid = start + (end - start) / 2;
      if (isBadVersion(mid))
        end = mid;
      else
        start = mid + 1;
    }
    return start;
  }
};