69-x的平方根

bergwhite 發(fā)布于2019-08-19 11:07 / 2068人閱讀

摘要：前言今天心血來潮想做一下題目，就選了一道關(guān)于二分查找的題目的平方根實現(xiàn)函數(shù)。計算并返回的平方根，其中是非負整數(shù)。示例輸入輸出示例輸入輸出說明的平方根是由于返回類型是整數(shù)，小數(shù)部分將被舍去。

前言

今天心血來潮想做一下題目，就選了一道關(guān)于二分查找的題目x的平方根：

實現(xiàn)int sqrt(int x)函數(shù)。
計算并返回 x 的平方根，其中 x 是非負整數(shù)。
由于返回類型是整數(shù)，結(jié)果只保留整數(shù)的部分，小數(shù)部分將被舍去。
示例 1:
輸入: 4
輸出: 2
示例 2:
輸入: 8
輸出: 2
說明: 8 的平方根是 2.82842..., 由于返回類型是整數(shù)，小數(shù)部分將被舍去。

解題思路

一開始我是直接用二分查找的做法來進行解題，但是其中一個測試用例為2147395599,進行平方的時候溢出導(dǎo)致結(jié)果錯誤。后面在網(wǎng)上找到一個關(guān)于平方的特性：
對于一個非負數(shù)n，它的平方根m不會大于（n/2+1），即m<=(m^2)/2+1
利用這個特性縮小了二分查找的范圍最終完成解題。

實現(xiàn)代碼

    public int mySqrt(int x) {
        //為了防止溢出，選擇用長整型
        long left=0;
        //對于一個非負數(shù)n，它的平方根不會大于 n/2+1
        long right=x/2+1;
        while(left<=right){//二分查找
            long middle = (left + right)/2;
            long middleSqrt=middle*middle;
            if(middleSqrt>x){
                right=middle-1;
            }else if(middleSqrt