leetcode 69 x的平方根

题目描述

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

题目来源：https://leetcode-cn.com/problems/sqrtx

解题思路

本题目有两种解法，一种是遍历判断，复杂度比较高；另一种则是二分算法。 本题主要讲述二分算法的使用。

两个模板

int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } return l; } int bsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } return l; }

两个模板的区别主要在于：经过判断后，对于左半部分，取 $[l,mid]$ 还是 $[l,mid)$，即 mid 的归属问题。 这里通过图解说明一下 (重点理解区间划分图)：

说明：

图中假定的是前半部分满足条件，后半部分不满足条件。如果改成前半部分不满足条件，后半部分满足条件。在 while 循环中，只需调换 if else 分支。mid 取值方式依赖于循环过程中 l 和 r 的取值方式。因为两种方法中 l 和 r 的取值方式不同，因此 mid 的取值方式也不同。在第二种方法中，如果 $mid=(l+r)>>1$，那么存在一种特殊情况，使得边界条件为 $[l,l+1]$，且 check(mid) 满足条件，此时将会进入死循环。为解决这种情况，只能取值 $mid=(l+r+1)>>1$。

二分一般步骤

确定二分的边界得到区间划分图书写代码

应用

确定二分的边界 数学知识：$0<=\sqrt{x}<=x$。因此 int l = 0,r = x;。得到区间划分图 采取性质 $nums[i]\ast nums[i]\le target$ 很容易得到下面的区间划分图，因此易知采取第二个模板。

根据题目，这里的 target 应该为 x。

当时我完成此题时，曾考虑为何不能采用如下性质 $nums[i]\ast nums[i]\ge target$，这里做一解答与总结。

书写代码int mySqrt(int x) { int l = 0,r = x; while(l < r) { int mid = l + (long long)r + 1 >> 1; // 强制类型转换防止溢出 if(mid <= (x / mid)) { l = mid; } else { r = mid - 1; } } return l; }