1 class Solution { 2 public: 3     int sqrt(int x) { 4         if (x <= 1) return x; 5         long long l = 1, r = x / 2 + 1; 6          7         while (l <= r) { 8             long long m = (l + r) / 2; 9             long long v = m * m;10             if (v == x) return m;11             else if (v < x) {12                 l = m + 1;13             } else {14                 r = m - 1;15             }16         }17         18         return r;19     }20 };