LeetCode-求一个数的平方根sqrt(x)

• 描述

  如题

• 思路

  使用基础算法，二分查找容易求出sqrt(x)。如果对精度有要求，即要求精确到小数点后n位：sqrt(x, n)，只不过此时二分查找的head和tail的偏移不再是1，而是与精度有关。

• 实现

  // 没有精度的要求
  class Solution {
  private:
      //int compute_count=0;
  public:
      // my sqrt without accuracy
      int mySqrt(int x) {
          int head = 0, tail=x;
          while(head<=tail){
              long long int middle = head + (tail-head)/2;
              if(middle * middle == x)
                  return middle;
              else if(middle * middle < x)
                  head = middle+1;
              else
                  tail = middle-1;
          }
          return tail;
      }
  
      // my sqrt with accuracy
      double mySqrt(double x, int acc){
          double head = 0.0;
          double offset = pow(10, -acc);
          double tail = x - offset;
          cout<<"Accuracy: "<<offset<<" result: ";
  
          while(tail>=head){
              //compute_count++;
              double mid = head + (tail-head)/2;
              if(mid * mid == x)
                  return mid;
              else if(mid * mid < x)
                  head = mid + offset;
              else
                  tail = mid - offset;
          }
          return return offset!=1?min(tail,head):tail;
      }
  };
  
  int main(){
      Solution sol;
      double in;
      cin>>in;
      // 调用无精度要求的函数
      cout<<sol.mySqrt(static_cast<int>(in))<<endl;
      // 不同的精度要求
      cout<<sol.mySqrt(in,0)<<endl;
      cout<<sol.mySqrt(in,1)<<endl;
      cout<<sol.mySqrt(in,2)<<endl;
      cout<<sol.mySqrt(in,3)<<endl;
      cout<<sol.mySqrt(in,4)<<endl;
      cout<<sol.mySqrt(in,5)<<endl;
      cout<<sol.mySqrt(in,6)<<" | true: "<<sqrt(in)<<endl;
  
      return 0;
  }

  返回如下，可以看出，结果的精度在随要求精度提高：

  87 # 输入87
  9
  Accuracy: 1 result: 9
  Accuracy: 0.1 result: 9.32656
  Accuracy: 0.01 result: 9.32678
  Accuracy: 0.001 result: 9.32655
  Accuracy: 0.0001 result: 9.32743
  Accuracy: 1e-05 result: 9.32738
  Accuracy: 1e-06 result: 9.32738 | true: 9.32738

敲黑板：注意边界条件，注意特殊情况。