1 class Solution: 2     # @param x, an integer 3     # @return an integer 4     def getVal(self, begin, end, x): 5         if end == begin : 6             return begin 7         if end == begin + 1: 8             return begin 9 10         while True:11             mid = (begin + end) / 212             tmp = mid * mid 13 14             if tmp == x:15                 return mid16             elif tmp < x: 17                 return self.getVal(mid, end, x)18             elif tmp > x:19                 return self.getVal(begin, mid, x)20 21     def sqrt(self, x):22         if x == 0: return 023 24         val = 1 25         while True:26             tmp  = val * val27 28             if tmp == x:29                 return val30             elif tmp > x:31                 return self.getVal(val/2, val, x)32             else:33                 val *= 2