**一. 題目描述** 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. **二. 題目分析** 題目說了一堆，一開始并不知道是想讓干什么。后來去網上查了題意，引用如下： 你是一名產品經理，并領導團隊開發一個新產品。不幸的是，產品的最終版本沒有通過質量檢測。由于每一個版本都是基于上一個版本開發的，因此某一個損壞的版本之后的所有版本全都是壞的。 假設有n個版本[1, 2, …, n]，現在你需要找出第一個損壞的版本，它導致所有后面的版本都壞掉了。 提供給你一個API?`bool isBadVersion(version)`，其功能是返回某一個版本是否損壞。實現一個函數找出第一個損壞的版本。你應該最小化調用API的次數。 原來只需實現類似于[Search for a Range](http://blog.csdn.net/liyuefeilong/article/details/50403616)?的功能，判斷壞版本的函數`bool isBadVersion(version)`題目已經提供，無需糾結如何操作，這里還是使用二分查找來解決問題。 **三. 示例代碼** 期初使用如下代碼一直提示：Time Limit Exceeded ~~~ // Forward declaration of isBadVersion API. bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { int low = 1, high = n; int midIndex = 0; while (low <= high) { midIndex = (low + high) / 2; if (isBadVersion(midIndex)) high = midIndex - 1; else low = midIndex + 1; } return low; } }; ~~~ 檢查了一段時間，發現當n取很大的數時出現問題，原來是語句`midIndex = (low + high) / 2;`?直接相加時溢出，導致循環超時，該用以下代碼Accept。 ~~~ // Forward declaration of isBadVersion API. bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { int low = 1, high = n; int midIndex = 0; while (low <= high) { midIndex = low + (high - low) / 2; if (isBadVersion(midIndex)) high = midIndex - 1; else low = midIndex + 1; } return low; } }; ~~~ **四. 小結** 該題的難度在[Search for a Range](http://blog.csdn.net/liyuefeilong/article/details/50403616)?之下，但出現了數據溢出的問題，因此對于簡單一些的題也時刻不能掉以輕心啊。