Java binary search O(lgn) solution without using "long" type to avoid overflow


  • 3
    N
    public boolean isPerfectSquare(int num){
            
            if(num <= 0) return false;
            
            int left = 1, right = num;
            
            while(left <= right){
                int mid = left + (right - left)/2;
                // use "/" to avoid overflow
                if(mid > num / mid){
                    right = mid - 1;
                }else if(mid < num / mid){
                    left = mid + 1;
                }else{
                    return num % mid == 0;
                }
            }
            return false;
        }
    

Log in to reply
 

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