/**
 * 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.
 *
 * Tags: Binary Search
 * Similar Problems: (M) Search for a Range (M) Search Insert Position
 */
public class FirstBadVersion {

    /**
     * pure binary search
     */
    public int firstBadVersion(int n) {
        int l = 1;
        int r = n;

        while (l < r) {
            int m = l + (r - l) / 2;
            if (!isBadVersion(m)) l = m + 1;
            else r = m;
        }
        return l;
    }

    /**
     * less loop improvement
     */
    public int firstBadVersion(int n) {
        int l = 1;
        int r = n;

        while (l < r) {
            int m = l + (r - l) / 2;
            if (!isBadVersion(m)) l = m + 1;
            else if (m == 1 || !isBadVersion(m - 1)) // two API calls but less loops
                return m;
            else r = m;
        }
        return l;
    }

}

@@ -1,12 +1,62 @@
+package com.freetymekiyan.algorithms.level.easy;%0A%0A
 /**%0A * You a
@@ -324,24 +324,28 @@
 also bad.%0A *
+ %3Cp%3E
 %0A * Suppose 
@@ -471,24 +471,28 @@
 o be bad.%0A *
+ %3Cp%3E
 %0A * You are 
@@ -682,16 +682,46 @@
  API.%0A *
+ %3Cp%3E%0A * Company Tags: Facebook
 %0A * Tags
@@ -779,16 +779,17 @@
  a Range
+,
  (M) Sea
@@ -807,16 +807,50 @@
 Position
+, (E) Guess Number Higher or Lower
 %0A */%0Apub
@@ -897,26 +897,242 @@
   * 
-pure binary search
+Binary Search.%0A     * n versions from 1 to n.%0A     * Get the middle version m.%0A     * If m is bad, which means m+1 to n are all bad, search in the left half.%0A     * If m is good, search in the right half.%0A     * Stop when l reaches r.
 %0A   
@@ -1267,32 +1267,88 @@
 l + (r - l) / 2;
+ // Avoid overflow, since l %3E= 1, n %3C= Integer.MAX_VALUE
 %0A            if 
@@ -1357,32 +1357,50 @@
 isBadVersion(m))
+ %7B%0A               
  l = m + 1;%0A    
@@ -1402,36 +1402,70 @@
 %0A           
+ %7D
  else 
-r = m;
+%7B%0A                r = m;%0A            %7D
 %0A        %7D%0A 
@@ -1507,29 +1507,404 @@
   * 
-less loop improvement
+Dummy function, just for compilation.%0A     */%0A    private boolean isBadVersion(int m) %7B%0A        return m %3E 1;%0A    %7D%0A%0A    /**%0A     * Binary Search. Pruning.%0A     * If we know m is a bad version, we can check m - 1 right after that.%0A     * If m - 1 is 1, which means that's the only available good version, m would be the first bad version.%0A     * If m - 1 is good, then m is the first bad version.
 %0A   
@@ -1930,32 +1930,33 @@
  firstBadVersion
+B
 (int n) %7B%0A      
@@ -2082,16 +2082,34 @@
 sion(m))
+ %7B%0A               
  l = m +
@@ -2119,24 +2119,26 @@
 %0A           
+ %7D
  else if (m 
@@ -2171,39 +2171,98 @@
 1)) 
-// two API calls but less loops
+%7B%0A                // Early return. If current version is bad and the previous one is good.
 %0A   
@@ -2299,20 +2299,54 @@
     
+ %7D
  else 
-r = m;
+%7B%0A                r = m;%0A            %7D
 %0A   

update first bad version