Sqrt(x)

二分法。基本思路是跟二分查找类似，要求是知道结果的范围，取定左界和右界，然后每次砍掉不满足条件的一半，直到左界和右界相遇。算法的时间复杂度是O(logx)，空间复杂度是O(1)。代码如下：

    int sqrt(int x) {
        if(x<0) return -1;
        if(x==0) return 0;
        int l=1,r=x/2+1;
        while(l<=r){
            int m=l+(r-l)/2;
            if(m<=x/m&&x/(m+1)<(m+1))
                return m;
            if(m<x/m)
                l=m+1;
            else r=m-1;   
        }
        return 0;
    }

//another flavor
    int sqrt(int x) {
      if(x<=1) return x;
   
      int left=0, right=x, mid;
   
      while( (right-left)>1 )
      {
        mid=left+(right-left)/2;
   
        if(mid==x/mid)
          return mid;
        else if(x/mid < mid)
          right=mid;
        else
          left=mid;
      }
   
      return left;

    }