NC32 #求平方根#

二分查找。
注意点：

• right直接设置为x/2因为当x>4时log2(x)<x/2。
• 注意int溢出！判断middle与x/middle的关系，而不是middle*middle与x的关系。

  class Solution {
  public:
    int sqrt(int x) {
        if(x == 0) return 0;
        else if(x == 1 || x == 2 || x == 3) return 1;
        else
        {
            int left = 1, right = x / 2;
            while(left <= right)
            {
                int middle = (left + right) / 2;
                if(middle <= x / middle && (middle + 1) > x / (middle + 1)) 
                    return middle;
                if(middle < x / middle) 
                    left = middle + 1;
                else 
                    right = middle - 1;
            }
        }
        return -1;
    }
  };