C++ Binary Search Solution. Easy understand


  • 4
    E
    class Solution {
    public:
    int mySqrt(int x)
    {
    	long long low = 0;
    	long long high = x;
    
    	while (low < high)
    	{
    		long long mid = (high - low) / 2 + low;
    
    		if (mid * mid == x)
    			return mid;
    		else if (mid * mid > x)
    			high = mid - 1;
    		else
    			low = mid + 1;
    	}
    
    	return low * low > x ? low - 1 : low;
    }
    };

  • 0
    J
    int mySqrt(int x) {
        if (x == 0) return 0;
        if (x < 4) return 1;
         int64_t i = 0;
         int64_t j = x/2;
         int64_t m = (i+j)/2;
        for(; i <= j && m != x/m ;m=(i+j)/2) {
            if (m*m < x) {
                i = m+1;
            } else {
              
                j = m -1;
            }
        }
        return m;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.