1 public class Solution {
 2     public int sqrt(int x) {
 3        if(x==0 ||x==1) return x;
 4        long start = 1;
 5        long end = x-1;
 6        while(start<=end){
 7            long mid = (start+end)/2;
 8            if(mid*mid==x)
 9             return (int)mid;
10             else if(mid*mid>x){
11                 end = mid-1;
12             }
13             else{
14                 start = mid+1;
15             }
16        }
17        return (int)(start+end) /2;
18     }
19 }