/**
 * Problem: #278 First Bad Version
 *
 * Idea:
 *
 * Solutions:
 *  firstBadVersion: uses basic binary search, but StackOverflowError occurs.
 *
 * Note: #canbefaster
 */

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */
public class FirstBadVersion {
    public int binarySearch(int left, int right) {
        int middle = left + (right-left)/2;

        if (isBadVersion(middle)) {
            if (!isBadVersion(middle - 1)) {
                return middle;
            } else {
                return binarySearch(left, middle-1);
            }
        } else {
            return binarySearch(middle + 1, right);
        }
    }

    public int firstBadVersion(int n) {
        return binarySearch(1, n);
    }

    private boolean isBadVersion(int n) {
        if (n >= 1702766719) return true;
        return false;
    }

    public static void main(String[] args) {
        System.out.println(new FirstBadVersion().firstBadVersion(2126753390));
    }
}

@@ -43,16 +43,84 @@
  * Idea:
+ brute force will exceed time limit, binary search is able to solve.
 %0A *%0A * S
@@ -159,14 +159,8 @@
 ses 
-basic 
 bina
@@ -201,16 +201,73 @@
 occurs.%0A
+ *  firstBadVersion2: standard binary search, efficient.%0A
  *%0A * No
@@ -528,16 +528,65 @@
 left)/2;
+ // (left + right)/2 may cause StackOverflowError
 %0A%0A      
@@ -884,60 +884,542 @@
 int 
-firstBadVersion(int n) %7B%0A        return binarySearch
+binarySearch2(int left, int right) %7B%0A        while (left %3C right) %7B%0A            int middle = left + (right-left)/2;%0A            if (isBadVersion(middle)) %7B%0A                right = middle;// might or might not be the one, so without -1%0A            %7D else %7B%0A                left = middle + 1; // definitely not the one, therefore +1%0A            %7D%0A        %7D%0A        return left;%0A    %7D%0A%0A    public int firstBadVersion(int n) %7B%0A        return binarySearch(1, n);%0A    %7D%0A%0A    public int firstBadVersion2(int n) %7B%0A        return binarySearch2
 (1, 
@@ -1492,18 +1492,14 @@
  %3E= 
-1702766719
+342354
 ) re
@@ -1652,18 +1652,94 @@
 ion(
-2126753390
+34252345));%0A        System.out.println(new FirstBadVersion().firstBadVersion2(34252345
 ));%0A

Add standard binary search