时间轴

2025-11-26

init

题目：

P69 x的平方根

https://leetcode.cn/problems/sqrtx/description/?envType=study-plan-v2&envId=top-interview-150

二分法：

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
class Solution {
    public:
	int mySqrt(int x)
	{
		if (x == 1 || x == 2) {
			return 1;
		}
		long left = 1, right = x, mid;
		long val1, val2;
		while (left <= right) {
			mid = (left + right) / 2;
			val1 = mid * mid;
			val2 = (mid + 1) * (mid + 1);

			if (val1 < x) {
				if (val1 < x && val2 > x) {
					return mid;
				} else {
					left = mid + 1;
				}

			} else if (val1 > x) {
				right = mid - 1;
			} else {
				return mid;
			}
		}
		return mid;
	}
};