思路

用按值二分在答案范围内搜索。记左右边界为 $l$ 与 $r$ 。当 $x \ge 2$ 时有

因此可取初始区间 $[l=1,r=\left\lfloor \dfrac{x}{2} \right\rfloor+1]$ ；当 $x<2$ 时直接返回 $x$ 。

在循环中取中点

P3451.第1题-求平方根

1000ms

Difficulty: 2

所属公司 : B站

算法与标签>二分算法

实现函数 int mysqrt(int x) 。

计算并返回 $x$ 的平方根(向下取整)

数据范围： $0<=x<2^{31}-1$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(logx)$

输入

输出

输入

2143195649

输出

输入

预期输出（选填）