Java Binary Search Solution with Explanation (O(log(n))


  • 0
    D

    So the idea is similar to the previous question about square root. We do a binary search start from the mid of num, then update left = mid + 1 if mid * mid is too small, or update right = mid if mid * mid is too large, both comparing to num. I use division to avoid overflow, and the num%mid == 0 is for cases such as num = 10 and our mid = 3, and we don't want to return true for this case even though in java mid = num/mid in here. Run time is O(log(n)) since we are halving the range in every iteration. Thanks for your time reading my answer.

    public boolean isPerfectSquare(int num) {
            if (num == 1) return true;
            int left = 0, right = num;
            
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (num%mid == 0 && mid == num/mid) return true;
                else if (mid <= num/mid) left = mid + 1;
                else right = mid;
            }
            
            return false;
        }

  • 0

    Why not use 'mid*mid == num'?


  • 0
    D

    @Izana To avoid overflow.


  • 0

    @dianhua1560 Yeah, I got it. I tried by myself and ooops....


Log in to reply
 

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