Leetcode–Sqrt(x)

The Problem:

Implement int sqrt(int x).

Compute and return the square root of x.

Notes:

  1. Like Divide two integers and Pow(x,n), a math problem in face is a search problem, here we use binary search.
  2. Note that when doing square, the result could exceed integer range, so we use long type to hold the value.
  3. Mistakes I made:
    1. condition for while loop is high>=low, not high > low
    2. In each step, either high or low will update, but should update to mid+-1 instead of mid, because if mid happens to be same as low, it will keep going to same branch and result in infinite loop.

Java Solution

public class Solution {
    public int sqrt(int x) {
        if(x==0 || x==1) return x;        
        long low= 1;
        long high = x;
        while(high >=low){   // not high>low  
            long mid = (low+high)/2;
            if(x==mid * mid)
                return (int)mid;
            if(x<mid*mid)
                high = mid-1;  // not high=mid 
            else
                low = mid+1;    
        }
        return (int)high;
    }
}
Advertisements

One thought on “Leetcode–Sqrt(x)

  1. Pingback: Leetcode–Search Insert Position | Linchi is coding

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s