算法1
思想:从(0, x)中找到t * t >= x的最小的数,有时候可能很难想left,right更新方式是什么,可以用以下方式思考
(1)画出当前mid的位置在哪?
(2)根据数组性质,看最终答案在哪?
(3)根据最终答案和当前mid的相对位置去更新left和right。还需要考虑到所选去见包不包括mid,以此来决定使用哪个模版。
时间复杂度:
O(logn)
C++ 代码
class Solution {
public:
int mySqrt(int x) {
int l = 0, r = x;
while(l < r)
{
int mid = l + r + 1ll >> 1; //1ll表示long long类型,只用int的话,leetcode会报错
if(mid * 1ll * mid <= x) l = mid; //mid左边是满足mid * mid <= x,此时我们需要找的数应该在mid右边,并且包括mid,用y神模版二。反过来想的话,如果更新方式为r = mid - 1,那么最终,mid值为0.
else r = mid - 1;
}
return r;
}
};