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

• 对于一个整数求解其平方根可以使用“二分法”和“牛顿法”。
• 所谓“二分法”就是不断地缩小平方根所在的范围，直到收敛到一个数。例如求解数k的平方根t，首先设置t的范围为[left, right](其中left和right分别初始化为1， k)，然后判断m=(l+k)/2与k的平方根t的关系，如果m比t小，则t的范围为[m+1， right]，否则为[left, m-1]，然后依次循环，直到left>=right终止。

int mySqrt(int x) {        if(x == 0)        {            return 0;        }        int left  = 1;        int right = x;        int ret = 0;        while(left <= right)        {            int mid = (left + right) / 2;            if(mid == x / mid)            {                return mid;            }            else if(mid > x/mid)            {                 right = mid - 1;            }            else            {                left = mid + 1;                   ret = mid;       //在 left 需要后移前，就要注意 平方根整数部分，相反 right 前移则不需要注意              }        }                return ret;    }

• 通过观察代码，我们可以发现其中有两处地方值得考虑，对于第一处判断可能很多人潜意识的会写成“mid * mid == k”，而第二处写成“mid * mid > k”，初看，这个貌似的确没有什么问题，但是在运行程序时可能会发现出现死循环现象。（我第一次写代码就出现了这样的问题）

• 为什么会出现这种情况呢？

  主要是因为在计算机中整型数据（int）是有位数限制的，一般是4个字节（32bits），这就可能出现“mid * mid”溢出的情况，这样在程序执行过程中就可能出现无限循环的情况。

• 因此，以后在程序设计过程中一定要特别注意不同类型数的位数的限制，避免因为溢出造成的逻辑错误，而且在能够同时使用乘法或者除法（注意考虑除数不能为0）时，尽量使用除法计算。

在做运算时，不仅要避免乘法可能会带来的问题，还需要考虑到加法可能或造成的溢出问题，对于“二分法”算法中求解"mid=left+right"就需要考虑右边可能因为溢出造成的结果错误，因此应该改成"mid=left+(right-left)/2".

二分法标准模板

int binarySearch(vector
   
    & nums, int target){  if(nums.size() == 0)    return -1;  int left = 0, right = nums.size() - 1;  while(left <= right)  {    // Prevent (left + right) overflow    int mid = left + (right - left) / 2;    if(nums[mid] == target)    {     	return mid;      }    else if(nums[mid] < target)     {    	 left = mid + 1;    }    else     {     	  right = mid - 1;     }  }  // End Condition: left > right  return -1;}
   

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