FilesExpand file tree

master

/

[69]x 的平方根 .java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

36 lines (31 loc) · 772 Bytes

master

/

[69]x 的平方根 .java

Copy path

Top

File metadata and controls

• Code
• Blame

36 lines (31 loc) · 772 Bytes

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

//leetcode submit region begin(Prohibit modification and deletion)

class Solution {

public int mySqrt(int x) {

//0和1快速返回，节省效率

if (x == 0 || x == 1) {

return x;

}

//左指针

int left = 1;

//右指针(因为除0 1 之外，其他的数的平方不会比他的二分之一大)

int right = x/2;

//二分法

while (left <= right) {

//中间值

int middle = (left + right) / 2;

//用除法可以有效的防止溢出

if (middle == x/middle) {

return middle;

}

//x的值在middle右边

if (middle < x/middle) {

left = middle + 1;

} else {

//x的值的大小在middle左边

right = middle - 1;

}

}

return left - 1;

}

}

//leetcode submit region end(Prohibit modification and deletion)