---
tags: LeetCode
---

# 278. First Bad Version
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose **you have n versions [1, 2, ..., n]** and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version. 

輸入範本如下

/* The isBadVersion API is defined in the parent class VersionControl.
      bool IsBadVersion(int version); */

public class Solution : VersionControl {
    public int FirstBadVersion(int n) {
        
    }
}

### 直覺想法
1. 暴力解

Time Limit Exceeded
public int FirstBadVersion(int n)
{
     for (int i = 1; i <= n; i++)
     {
          if (IsBadVersion(i))
          {
               return i;
          }
     }
     throw new Exception("not found");
}

2. 二分搜尋法(iterator)
- 此題與一般二分搜尋不同的是透過比較數值相等就可以知道是否為正確答案.
當 IsBadVersion(mid) 為 true , 代表找到壞版本 , 但仍然必須去確認是否為第一個壞版本 , 所以接著使用 right = mid 去查詢左側數值 ( 不使用 right = mid -1 ) 是因為 mid 可能就是第一個壞版本 .

    32 ms	14.7 MB
    You are here!
    Your runtime beats 98.81 % of csharp submissions.
    public int FirstBadVersion(int n)
    {
         int left = 1, right = n;
         while (left < right) // 不能使用 left <= right , 因為當 left == right 且 n = (left+right)/2 為壞版本時 , 會無窮迴圈
         {
              int mid = left + (right - left) / 2;
              if (IsBadVersion(mid))
              {
                   right = mid; // 不能使用 mid - 1
              }
              else
              {
                   left = mid + 1;
              }
         }
         return left; // 使用 right 也可以. 因為此時 left = right
    }

3. 二分搜尋法(遞迴)

    public int FirstBadVersion(int n)
    {
        return FirstBadVersion(1, n);

        int FirstBadVersion(int left, int right)
        {
            int mid = left + (right - left) / 2;
            if (left < right)
            {
                return IsBadVersion(mid) ? 
                FirstBadVersion(left, mid ) : FirstBadVersion(mid + 1, right);
            }
            return left; // 使用 right 也可以. 因為此時 left = right
        }
    }

### Thank you!

You can find me on

- [GitHub](https://github.com/s0920832252)
- [Facebook](https://www.facebook.com/fourtune.chen)

若有謬誤 , 煩請告知 , 新手發帖請多包涵

# :100: :muscle: :tada: :sheep: