day6

url:https://www.lintcode.com/problem/sqrtx/description
06.Sqrt(x)
Description
Implement int sqrt(int x).
Compute and return the square root of x.

Example
Example 1:
	Input:  0
	Output: 0
  
Example 2:
	Input:  3
	Output: 1
	
	Explanation:
	return the largest integer y that y*y <= x. 
	
Example 3:
	Input:  4
	Output: 2
  
----------------------------------------------------------------------------  
class Solution:
    """
    @param x: An integer
    @return: The sqrt of x
    """
    def sqrt(self, x):
        # write your code here
        start = 0
        end = x 
        res = 0
        while start<=end:
            mid = start + (end-start)//2
            if mid*mid<=x:
                start =mid+1
                res = mid
            else:
              end = mid-1
        return res