package com.fishercoder.solutions;

/**
 * 278. First Bad Version
 *
 * 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.
 *
 * Example:
 * Given n = 5, and version = 4 is the first bad version.
 * call isBadVersion(3) -> false
 * call isBadVersion(5) -> true
 * call isBadVersion(4) -> true
 * Then 4 is the first bad version.
 * */
public class _278 {

	public static class Solution1 {
		public int firstBadVersion(int n) {
			int left = 1;
			int right = n;
			while (left < right) {
				int mid = left + (right - left) / 2;
				if (isBadVersion(mid)) {
					right = mid;
				} else {
					left = mid + 1;
				}
			}
			return left;
		}

		private boolean isBadVersion(int left) {
			//this is a fake method to make Eclipse happy
			return false;
		}
	}
}

@@ -33,1187 +33,461 @@
 s;%0A%0A
-/**%0A * 278. First Bad Version%0A *%0A * You are a product manager and currently leading a team to develop a new product.%0A * Unfortunately, the latest version of your product fails the quality check.%0A * Since each version is developed based on the previous version, all the versions 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,%0A * which causes all the following ones to be bad.%0A *%0A * You are given an API bool isBadVersion(version) which will return whether version is bad.%0A * Implement a function to find the first bad version. You should minimize the number of calls to the API.%0A *%0A * Example:%0A * Given n = 5, and version = 4 is the first bad version.%0A * call isBadVersion(3) -%3E false%0A * call isBadVersion(5) -%3E true%0A * call isBadVersion(4) -%3E true%0A * Then 4 is the first bad version.%0A * */%0Apublic class _278 %7B%0A%0A%09public static class Solution1 %7B%0A%09%09public int firstBadVersion(int n) %7B%0A%09%09%09int left = 1;%0A%09%09%09int right = n;%0A%09%09%09while (left %3C right) %7B%0A%09%09%09%09int mid = left + (right - left) / 2;%0A%09%09%09%09if (isBadVersion(mid)) %7B%0A%09%09%09%09%09right = mid;%0A%09%09%09%09%7D else %7B%0A%09%09%09%09%09left = mid + 1;%0A%09%09%09%09%7D%0A%09%09%09%7D%0A%09%09%09return left;%0A%09%09%7D%0A%0A%09%09
+public class _278 %7B%0A%0A    public static class Solution1 %7B%0A        public int firstBadVersion(int n) %7B%0A            int left = 1;%0A            int right = n;%0A            while (left %3C right) %7B%0A                int mid = left + (right - left) / 2;%0A                if (isBadVersion(mid)) %7B%0A                    right = mid;%0A                %7D else %7B%0A                    left = mid + 1;%0A                %7D%0A            %7D%0A            return left;%0A        %7D%0A%0A        
 priv
@@ -523,19 +523,28 @@
 left) %7B%0A
-%09%09%09
+            
 //this i
@@ -585,11 +585,20 @@
 ppy%0A
-%09%09%09
+            
 retu
@@ -611,13 +611,22 @@
 se;%0A
-%09%09%7D%0A%09
+        %7D%0A    
 %7D%0A%7D%0A

refactor 278