leetcode4/Sqrt.java at master · 1code/leetcode4 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public class Solution {
    public int sqrt(int x) {
        // Start typing your Java solution below
        // DO NOT write main() function
    	if(x==0) return 0;
		if(x==1) return 1;

		int i = 0;
		int j;

		if(x<46340*2)
			j= x;
		else
			j = 46340;

		while(j>i){
			int m = (i+j)/2;
			if(m*m == x)
				return m;
			else if((m*m)>x)
				j = m-1;
			else{
				if(((m+1)*(m+1))>x)
					return m;
				else
					i = m+1;
			}
		}

		if(i*i>x)
			return i-1;
		else
			return i;


    }
}

//Better version
public class Solution {
    public int sqrt(int x) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (x < 1)
            return 0;
        if (x == 1)
            return 1;

        int mid = x/2;

        while (mid * mid > x || mid > 46340) {
            mid = (mid + x/mid)/2;
        }
        return mid;
    }
}