FilesExpand file tree

 master

/

sqrt.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

46 lines (41 loc) · 1.08 KB

 master

/

sqrt.java

Copy path

Top

File metadata and controls

• Code
• Blame

46 lines (41 loc) · 1.08 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/**

* Created by codingBoy on 17/2/7.

*/

public class sqrt

{

/**

*

* Implement int sqrt(int x).

* Compute and return the square root of x.

*

* 计算并返回x的平方根

*/

//二分查找法

public static int mySqrt(int x) {

if (x == 0)

return 0;

int left = 1, right = x;

while (true) {

int mid = left + (right - left)/2;

if (mid > x/mid) {

right = mid - 1;

} else {

if (mid + 1 > x/(mid + 1))

return mid;

left = mid + 1;

}

}

}

//方法二

// Explanation

//

// Apparently, using only integer division for the Newton method works. And I guessed that if I start at x, the root candidate will decrease monotonically and never get too small.

//

// The above solutions all got accepted, and in C++ I also verified it locally on my PC for all possible inputs (0 to 2147483647):

/**

* long r = x;

while (r*r > x)

r = (r + x/r) / 2;

return (int) r;

*/

}