題目描述

• Implement int sqrt(int x).
• Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
• Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

題目解讀

• 看代碼即可

代碼

• 思路一

#include<stdio.h>

int mySqrt(int x)
{
    int i,flag=0;

    if(x==1){
        return 1;
    }
    else{
       for(i=0;i<=x/2;i++){  
          if(i*i - x <= 0){
            flag=i;
          }
          else{
             flag = i-1;
             break;
          }
       }
    }
    return flag;
}
int main()
{
   printf("%d\n", mySqrt(2147395600));
}

• 思路二 二分查找遞歸實(shí)現(xiàn)

class Solution {
public:
    int mySqrt(int x) {
        if(x == 0 || x == 1){
            return x;
        }
        
        return BinarySearch(0, x/2, x);
    }
    
    int BinarySearch(int left, int right, int target){
        int med = (left + right) / 2;
        if((double)med*med - (double)target < 0){
            if((double)(med+1)*(med+1) - (double)target > 0){
                return med;
            }
            return BinarySearch(med+1, right, target);
        }
        else if((double)med*med - (double)target > 0){
            if((double)(med-1)*(med-1) - (double)target < 0){
                return med-1;
            }
            return BinarySearch(left, med-1, target);
        }
        else{
            return med;
        }
    }
};

• 思路三 二分查找循環(huán)實(shí)現(xiàn)

class Solution {
public:
    int mySqrt(int x) {
        if(x == 0 || x == 1){
            return x;
        }
        
        int result = 0;
        int left = 0;
        int right = x/2;
        int med = 0;
        
        while(left <= right){
            med = (left + right) / 2;    
            if((double)med*med - (double)x < 0){
                if((double)(med+1)*(med+1) - (double)x > 0){
                    result = med;
                    break;
                }
                left = med + 1;
            }
            else if((double)med*med - (double)x > 0){
                if((double)(med-1)*(med-1) - (double)x < 0){
                    result = med-1;
                    break;
                }
                right = med-1;
            }
            else{
                result = med;
                break;
            }
        }
        return result;
    }
};

總結(jié)展望

• 思路一到思路三，效率逐步提高