binary Search

class Solution {
public:
    int mySqrt(int x) {
        // the sqrt is not more than (x/2 + 1)
        int left =0 , right = x/2 + 1;
        //binary search
        while(left <= right){
            int mid = (left + right)/2;
            // using long long , cause mid*mid may overflow 
            long long sq = (long long)mid*(long long)mid;
            if(sq == x){
                return mid;
            }
            else if(sq > x){
                right = mid - 1;
            }
            else{
                left = mid + 1 ;
            }
        }
       //key , if there is not a precise sqrt, then return (mid-1) ,eg: for 3 ,return 1;for 5,return 2;
       return right;
    }
};