/**
 * Implement int sqrt(int x).
 * Compute and return the square root of x.
 *
 * Tags: Math, Binary Search
 */
class Sqrt {
    public static void main(String[] args) {
        int[] nums = {  -1, 1, 2, 4, 9, 16, 25 };
        for (int i = 0; i < nums.length; i++) {
            System.out.println(sqrt(nums[i]));
        }
    }

    /**
     * Validate input first
     * Binary Search from 1 ~ x
     * 
     * Negative?
     * Perfect square?
     * Note possible overflows when mid * mid or (left + right) / 2.
     */
    public static int sqrt(int x) {
        if (x < 0) return -1; // if (x <= 0) return x;
        if (x == 0) return 0;
        int left = 1; // search range
        int right = x;
        int mid;

        while (left <= right) { // can equal
            mid = left + (right - left) / 2; // left + right can overflow
            if (mid == x / mid) return mid; // mid * mid can overflow
            else if (mid > x / mid) right = mid - 1; // not right = mid
            else left = mid + 1; // break equal
        }

        return right;
    }
}
@@ -1,12 +1,113 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport org.junit.Assert;%0Aimport org.junit.Test;%0A%0A
 /**%0A * Imple
@@ -128,16 +128,23 @@
 int x).%0A
+ * %3Cp%3E%0A
  * Compu
@@ -185,42 +185,157 @@
 .%0A *
-%0A * Tags: Math, Binary Search%0A */%0A
+ %3Cp%3E%0A * Company Tags: Bloomberg, Apple, Facebook%0A * Tags: Binary Search, Math%0A * Similar Problems: (M) Pow(x, n) (M) Valid Perfect Square%0A */%0Apublic 
 clas
@@ -347,398 +347,522 @@
 t %7B%0A
+%0A
     
-public static void main(String%5B%5D args) %7B%0A        int%5B%5D nums = %7B  -1, 1, 2, 4, 9, 16, 25 %7D;%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            System.out.println(sqrt(nums%5Bi%5D));%0A        %7D%0A    %7D%0A%0A    /**%0A     * Validate input first%0A     * Binary Search from 1 ~ x%0A     * %0A     * Negative?%0A     * Perfect square?%0A     * Note possible overflows when mid * mid or (left + right) / 2
+/**%0A     * Binary Search.%0A     * Validate input first.%0A     * If x %3C 0 , invalid.%0A     * Special cases:%0A     * If x = 0 or 1, return x.%0A     * %3Cp%3E%0A     * Binary Search from 1 ~ x/2.%0A     * While lo %3C hi:%0A     * %7C Rounding mid up since if sqrt always return the ceiling.%0A     * %7C Compare mid with x / mid.%0A     * %7C If mid = x / mid, square root found, return mid.%0A     * %7C If mid %3E x / mid, mid shall not be square root, hi = mid-1.%0A     * %7C If mid %3C x / mid, mid can be square root, lo = mid.%0A     * Return hi
 .%0A  
@@ -882,20 +882,15 @@
 lic 
-static 
 int 
-s
+myS
 qrt(
@@ -917,77 +917,46 @@
 (x %3C
- 0) return -1; // if (x %3C= 0) return x;%0A        if (x == 0) return 0;
+= 1) %7B%0A            return x;%0A        %7D
 %0A   
@@ -969,118 +969,64 @@
 nt l
-eft
+o
  = 1;
- // search range%0A        int right = x;%0A        int mid;%0A%0A        while (left %3C= right) %7B // can equal
+%0A        int hi = x / 2;%0A        while (lo %3C hi) %7B
 %0A   
@@ -1038,139 +1038,164 @@
     
+int 
 mid = l
-eft
+o
  + (
-right - left) / 2; // left + right can overflow%0A            if (mid == x / mid) return mid; // mid * mid can overflow
+hi - lo + 1) / 2; // Rounding up.%0A            int t = x / mid;%0A            if (mid == t) %7B // Square root found.%0A                return mid;
 %0A   
@@ -1198,24 +1198,26 @@
 %0A           
+ %7D
  else if (mi
@@ -1224,133 +1224,495 @@
 d %3E 
-x / mid) right = mid - 1; // not right = mid%0A            else left = mid + 1; // break equal%0A        %7D%0A%0A        return right;
+t) %7B // Square root cannot be mid. Must in mid's left.%0A                hi = mid - 1;%0A            %7D else %7B // Square root can be mid, since it can be the ceiling.%0A                lo = mid;%0A            %7D%0A        %7D%0A        return hi;%0A    %7D%0A%0A    @Test%0A    public void testExamples() %7B%0A        int%5B%5D nums = %7B-1, 1, 2, 4, 9, 16, 25%7D;%0A        int%5B%5D res = %7B-1, 1, 1, 2, 3, 4, 5%7D;%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            Assert.assertEquals(res%5Bi%5D, mySqrt(nums%5Bi%5D));%0A        %7D
 %0A   

update sqrt