一. 题目描写叙述

Implement int sqrt(int x).

Compute and return the square root of x.

二. 题目分析

该题要求实现求根公式，该题还算是比較简单的，由于仅仅需返回最接近的整数，直接二分法就可以。在实现的过程中还是有一些细节的，比方推断条件：x / mid > mid而不能是x > mid * mid。由于mid * mid会导致溢出。

三. 演示样例代码

#include 
      
       using namespace std;class Solution{public:    int sqrt(int x)    {        if (x == 0 || x == 1) return x;        int min = 1, max = x / 2; // 根必在此区间中        // 二分查找        int mid, result;        while (min <= max)        {            mid = min + (max - min) / 2;            if (x / mid > mid)            {                               // 根的平方需小于等于x，因此每次须在此处更新根的值                result = mid;                 min = mid + 1;            }            else if (x / mid < mid) max = mid - 1;            else return mid;        }        return result;    }};
      

一些执行结果：

四. 小结

此题为分治思路的经典题型之中的一个。