Sharing my simple and clear solution


  • 0
    Z
    int sqrt(int x) {
        if(x == 0 || x == 1){
            return x;
        }
        int start = 1, end = x / 2;
        while(start <= end){
            int mid = start + (end - start) / 2;
            if(mid == x / mid){
                return mid;
            }
            if(mid < x / mid){
                start = mid + 1;
            }
            else{
                end = mid - 1;
            }
        }
        return start - 1;
    }
    

    The basic idea is binary search. Please notice that this function returns start - 1 in the end. It's because start will be always greater than result by one after while loop.


  • 0
    W

    I think just return end instead is ok.


Log in to reply
 

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