leetcode筆記：Sqrt(x)

一. 題目描述

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;
    }
};

一些運行結果：

四. 小結

此題為分治思路的經典題型之一。