I wonder why this solution is right and how about if I changed it?


  • 0
    D
    public static int sqrt(int x) {
            
    	 if( x == 0 || x == 1){
             return x;
         }
         long start = 0;
         long end = x;
      
         
         while ( end-start > 1){
             long mid = (int)(end + start) / 2;
             long s = mid * mid;
             
             if(s == x){
                 return (int)mid;
             }
             else if(s > x){
                 end = mid;
             }
             else {
                 start = mid;
             }
         
         }
         
         return (int)start;
        }
    

    Above is the working code snippet. I have questions as below. Thank you in advance for helping. ;-)

    1. While(end-start > 1) why we need 1 here? just because the return
      signiture is int?
      1. If we change while loop from while(end-start > 1) to while(end > start), we have to make end = mid-1; and start = mid + 1, correct?
      2. Why we cannot return end? or (int)(start+end)/2?? I saw almost 99% answer return to the left bound of binary search.

  • 0
    K

    Here is my thought. Notice that:

    (1) when x==0 or x==1 the program will just return x

    (2) there is a test case for s==x when mid (an integer) is exactly the square root of x,

    Therefore, it is guaranteed that in the while loop the true value of the square root of x (probably not an integer) will always be strictly smaller than end and strictly bigger than start. So we don't need things like mid-1 or mid+1. See it as a shrinking open interval.

    When we reach the condition end == start + 1, say 3 and 4, the true value is sure to be 3.xx, so we can just return 3 because the return type is int. There is no need for further search.

    BTW, long is involved because mid * mid may overflow int.


Log in to reply
 

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