Sqrt(x) (Java)

Leetcode

Implement int sqrt(int x).

Compute and return the square root of x.

Solution: remember that the sqrt of an number must less than  its half, than we we can apply binary search to find our target. pleas don't forget the overflow risk

	Implement int sqrt(int x).
	Compute and return the square root of x.
	Time complexity O(lgn)
	public class Sqrt {
	public int sqrt(int x) {
	if (x<0){
	return-1;
	}
	// in case of x==1
	long high=x/2+1;
	long low=0;
	while(low<=high){
	long mid=low+(high-low)/2;
	long sq=mid*mid;
	if (sq==(long)x){
	return (int)mid;
	}
	else if (sq<(long)x){
	low=mid+1;
	}
	else{
	high=mid-1;
	}
	}
	return (int)high;
	}
	}

view raw sqrt(x).java hosted with ❤ by GitHub