Sqrt(x) [Leetcode]

Implement int sqrt(int x).
Compute and return the square root of x.

Solution: binary search; pay attention to the overflow; we note that it is possible to get overflow when you compute the square of a large number or compute the average of two large numbers. For example, we have two integers a and b, if we compute the average of a and b by (a+b)/2, it is possible to get overflow, so the good way is to compute the average by a+(b-a)/2. Anyway, in this problem, we need to compute square of a large number, so here we use "long long" to avoid the overflow introducing by operating "int". [other good solutions: 1, 2]

class Solution {
public:
    int sqrt(int x) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(x<=0) return 0;
        if(x==1) return 1;
        long long start = 0, end = x;
        while(start<=end){
            //long long mid = (start+end)/2;
            long long mid = start+(end-start)/2;
            long long s = mid*mid;
            if(s==x)
                return mid;
            if(s<x)
                start = mid+1;
            else
                end = mid-1;
        }
        return start*start<=x?start:start-1; 
    }
};