# The Problem:

Implement `int sqrt(int x)`

.

Compute and return the square root of *x*.

# Notes:

- Like Divide two integers and Pow(x,n), a math problem in face is a search problem, here we use binary search.
- Note that when doing square, the result could exceed integer range, so we use long type to hold the value.
- Mistakes I made:
- condition for while loop is high>=low, not high > low
- 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

Pingback: Leetcode–Search Insert Position | Linchi is coding