本文共 1786 字，大约阅读时间需要 5 分钟。

一、题目描述

实现 int sqrt(int x) 函数。

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

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

二、解题思路

使用二分查找法（又叫折半查找法），这里就详细讲解一下数据结构中的二分查找法吧：

将表中间middle=4对应的关键字与查找关键字比较，如果两者相等则查找成功，否则利用中间位置记录将表分成前后两个子表，如果中间记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足天哦建的记录，是查找成功，或直到子表不存在，此时查找不成功。其中每一次的middle=(left+right)/2，向下取整。

三、代码编写步骤：

第一步：特殊值判断，将0和1这两个值排除

第二步：给出平方根要搜索的的区域left=1；right=x/2

第三步：下面为mid赋值，然后进行判断：mid>x/mid，其实就是mid*mid>x的判断，如果成立说明x的平方根应该是在[left，mid-1]

如果不成立则下一个搜索空间应该是[mid，right] 。

四、代码演示

class Solution {
       public int mySqrt(int x) {
           // 特殊值判断        if (x == 0) {
               return 0;        }        if (x == 1) {
               return 1;        }        int left = 1;        //如果x是一个奇数，right是向下取整的。        int right = x / 2;  //这里是向下取整的        // 在区间 [left..right] 查找目标元素        while (left < right) {
               //计算出来的带小数的都向上取整            int mid = (left+right)/2+1;            // 注意：这里为了避免乘法溢出，改用除法            if (mid > x / mid) {
                   // 下一轮搜索区间是 [left..mid - 1]                right = mid - 1;            } else {
                   // 下一轮搜索区间是 [mid..right]                left = mid;            }        }        return left;    }}

第16行：之所以(left+right)/2+1中加1是因为除法是向下取整的，所以在第12行计算right时实际的搜索空间是变小了的，假如x=0，这里x/2=4，比自身的一半小。在计算一些特例如4时，它的平方根就是自身的一半，所以不合适。还有一个原因是：

我这里以数字9为例，且mid= (left+right)/2计算式我不加1，我们来分析一下：

第一轮循环：left=1，right=4，mid=2

在第18行判断时mid>x/mid返回的是false，走else里面的代码此时left=2。

第二轮循环：left=2，right=4，mid=3

在18行判断时mid>x/mid返回的是false，走else里面的代码此时left=3。

第三轮循环：left=3，right=4，mid=3

在18行判断时mid>x/mid返回的是false，走else里面的代码此时left=3。

有没有发现第三次循环left=mid=3进入了死循环，就算再进行循环left还是等于3。这也是为什么这里需要加1向上取整的原因。

有没有发现第三次循环left=mid=3进入了死循环，就算再进行循环left还是等于3。这也是为什么这里需要加1向上取整的原因。

转载地址：http://xogki.baihongyu.com/