Sqrt

Implementint sqrt(int x).

Compute and return the square root ofx, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input:
 4

Output:
 2

Example 2:

Input:
 8

Output:
 2

Explanation:
 The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

While (start <= end) . 8 -> start = 3 end = 3

class Solution {
    public int mySqrt(int x) {
        int start = 1; 
        int end = x;
        while (start <= end) {
            long mid = start + (end - start) / 2;
            if(mid * mid == x) {
                return (int) mid;
            }else if (mid * mid < x) {
                start = (int)mid + 1;
            }else {
                end = (int)mid - 1;
            }
        }
        System.out.println("start: " + start);
        System.out.println("end: " + end);
        if(end * end <= x) {
            return end;
        }else {
            return start;
        }
    }
}

if int mid = start + (end - start) / 2;

if start is already really big, then mid will overflow

Input:

2147395599

Output:

2147395599

Expected:

46339

Stdout:

start: 2147395600 end: 2147395599