# 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)$

- 程式碼

    // 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;
        }
    };