lc-69

//Given a non-negative integer x, compute and return the square root of x. 
//
// Since the return type is an integer, the decimal digits are truncated, and on
//ly the integer part of the result is returned. 
//
// Note: You are not allowed to use any built-in exponent function or operator, 
//such as pow(x, 0.5) or x ** 0.5. 
//
// 
// Example 1: 
//
// 
//Input: x = 4
//Output: 2
// 
//
// Example 2: 
//
// 
//Input: x = 8
//Output: 2
//Explanation: The square root of 8 is 2.82842..., and since the decimal part is
// truncated, 2 is returned. 
//
// 
// Constraints: 
//
// 
// 0 <= x <= 231 - 1 
// 
// Related Topics Math Binary Search 
// 👍 4388 👎 3407


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int mySqrt(int x) {
        if (x == 0 || x == 1) {
            return x;
        }

        if (x < 4) {
            return 1;
        }

        long start = 2l, end = x / 2;

        while (start <= end) {
            if (start == end) {
                return (int)start;
            }

            if (start + 1 == end) {
                if (end * end <= x) {
                    return (int)end;
                } else {
                    return (int)start;
                }
            }

            long mid = start + (end - start) / 2;

            if (mid * mid == x) {
                return (int)mid;
            } else if (mid * mid < x) {
                start = mid;
            } else {
                end = mid;
            }
        }

        return -1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)