Solve this problem with Binary Search


  • 45
    class Solution {
    public:
        int sqrt(int x) {
            if (0 == x) return 0;
            int left = 1, right = x, ans;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (mid <= x / mid) {
                    left = mid + 1;
                    ans = mid;
                } else {
                    right = mid - 1;
                }
            }
            return ans;
        }
    };

  • 1
    H

    I used the similar way to binary search it, the difference is I used if (mid*mid <= x) instead of if (mid <= x / mid), but I got TLE...Does anybody know why?


  • 2
    Z

    mid * mid will overflow when mid > sqrt(INT_MAX)


  • 0
    H

    Thanks a lot!


  • 0
    B

    @Stomach_ache I used the following approach, which is very similar to a basic binary search. However, it doesn't give me the correct output. Could you please let me know why you check for mid <= x / mid and update ans anyway? What made you not use the typical binary search (like the way I have implemented it below)?

    class Solution {
    public:
        int mySqrt(int x) {
            if(x==0 || x==1)
                return x;
                
            int start=0, end=x, mid=0;
            while(start<=end) {
                mid=start+(end-start)/2;
                if(mid*mid==x)
                    return mid;
                else
                    if(mid*mid<x)
                        start=mid+1;
                    else
                        end=mid-1;
            }
            
            return mid;
        }
    };
    

  • 3

    @BatCoder There're two points I need to explain a bit.

    Firstly, the rationale behind mid <= x / mid instead of using mid * mid <= x is just for preventing from overflow (multiply two int numbers may not fit in int as well).

    Secondly, the meaning of ans in my code is used to keep the biggest integer which satisfies ans * ans <= x and then it'll be the answer at the end of binary search procedure.

    I noticed that you made mid as the final answer at the last line in your code, which may not satisfy mid * mid <= x cause you never know which branch of conditions mid will go at the last round of binary search.
    And btw, the input is not necessary a perfect square number, so that's why you should keep the largest integer that satisfies ans * ans <= x.

    Hope this help.

    BR


  • 0
    B

    @Stomach_ache This is helpful, thank you! :)


  • 0
    F

    @Stomach_ache Excellent explanation of the nuances of this algorithm. Thank you.


  • 0

    Actually I think 'right' can be set to (x/2) at the beginning. Because sqrt of a number will always be smaller or equal to 1/2 of this number. So the range of binary search can be set to (1, x/2). The running time should be better


  • 0

    @marriema Yes, that is right.

    But that does not actually matter so much since in Binary Search, iteration range being doubled only means exactly one more iteration done. This is something worth mentioning in an actual interview, but not something likely to produce noticeable running time difference to an OJ.


Log in to reply
 

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