---
# System prepended metadata

title: LeetCode 278. First Bad Version
tags: [Leetcode]

---

# LeetCode 278. First Bad Version
[LeetCode 278. First Bad Version]([leetcode_url](https://leetcode.com/problems/first-bad-version/description/)) (難度 通過率)
<!-- 
(<font color=#00AF9B>Easy</font> 53.8%) 
(<font color=#FFB800>Medium</font> 39.6%)
(<font color=#FF375F>Hard</font>)
 -->
    
- 限制 :

    <ul>
    <li><code>1 <= bad <= n <= 2^31 - 1</code></li>
    
    </ul>

- Solution

    這題是我想多了，多加了 direction 進去，導致程式變得很難寫，其實也是簡單的 binary tree 而已。(寫好久還 debug 半天...)
    要注意，起始值是 1 。
    - 時間複雜度: $O(lg(n))$
    - 空間複雜度: $O(1)$

- 程式碼
    ```c++=
    // The API isBadVersion is defined for you.
    // bool isBadVersion(int version);

    class Solution {
    public:
        int firstBadVersion(int n) {
            int older_version = 1, newer_version = n;
            int now_version = (newer_version - older_version)/2 + older_version;

            // true : direct to right, false: direct to left.
            bool dir = true; 
            while(older_version <= newer_version)
            {
                now_version = (newer_version - older_version)/2 + older_version;
                if(older_version == now_version && now_version == newer_version) break;
                cout << older_version << ' '<< now_version<< ' '<<newer_version <<endl;
                if(isBadVersion(now_version) == false)
                {
                    older_version = now_version + 1;
                }
                else
                {
                    dir = false;
                    newer_version = now_version;
                }
            }
            return now_version;
        }
    };
    ```
