@@ -0,0 +1,1450 @@
+/**%0A * You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of%0A * your product fails the quality check. Since each version is developed based on the previous version, all the versions%0A * after a bad version are also bad.%0A *%0A * Suppose you have n versions %5B1, 2, ..., n%5D and you want to find out the first bad one, which causes all the following%0A * ones to be bad.%0A *%0A * You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to%0A * find the first bad version. You should minimize the number of calls to the API.%0A *%0A * Tags: Binary Search%0A * Similar Problems: (M) Search for a Range (M) Search Insert Position%0A */%0Apublic class FirstBadVersion %7B%0A%0A    /**%0A     * pure binary search%0A     */%0A    public int firstBadVersion(int n) %7B%0A        int l = 1;%0A        int r = n;%0A%0A        while (l %3C r) %7B%0A            int m = l + (r - l) / 2;%0A            if (!isBadVersion(m)) l = m + 1;%0A            else r = m;%0A        %7D%0A        return l;%0A    %7D%0A%0A    /**%0A     * less loop improvement%0A     */%0A    public int firstBadVersion(int n) %7B%0A        int l = 1;%0A        int r = n;%0A%0A        while (l %3C r) %7B%0A            int m = l + (r - l) / 2;%0A            if (!isBadVersion(m)) l = m + 1;%0A            else if (m == 1 %7C%7C !isBadVersion(m - 1)) // two API calls but less loops%0A                return m;%0A            else r = m;%0A        %7D%0A        return l;%0A    %7D%0A%0A%7D%0A

add 278 FirstBadVersion