Sqrt(x) @LeetCode

Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

	package leetcode.binarySearch;
	/**
	* Solution: BinarySearch
	*
	* Tricky:
	* 1. Misunderstand the question, input 5,output 2; input 2,output 1. If not found, return the closest but not -1;
	* 2. I am not sure if 99 return 9 or 10, according to wrong answer, it seems like to be 9 even if 10 is closer.
	* 3. Input:2147395599, Output:2147395598, Expected:46339 the problem here is overflow x=500000 25000*25000<1000000
	* 4. we need to change mid * mid < target --> mid < target/mid if we use int !
	* 5. We could use long instead of int because of operation complexity of int
	* 6. to make it more efficient, the end should be x/2+1, squre(x/2+1) always >= square(x) !!!
	*
	* @author jeffwan
	*
	*/
	public class Sqrt {
	public int sqrt(int x) {
	int start, end, mid;
	start = 0;
	end = x / 2 + 1;
	while(start + 1 < end) {
	mid = start + (end - start) / 2;
	if (mid == x / mid) {
	return mid;
	} else if (mid < x / mid) {
	start = mid;
	} else {
	end = mid;
	}
	}
	if (start == x / start) {
	return start;
	}
	if (end == x / end) {
	return end;
	}
	return start;
	}
	// Use long to prevent overflow
	public int sqrt2(int x) {
	if (x < 0) {
	return -1;
	}
	long start, end, mid;
	start = 0;
	end = x ;
	while (start + 1 < end) {
	mid = start + (end - start) / 2;
	long square = mid * mid;
	if ((long)x == square) {
	return (int)mid;
	} else if ((long)x < square ) {
	end = mid;
	} else {
	start = mid;
	}
	}
	if ((long)x == start * start) {
	return (int)start;
	}
	return (int)start;
	}
	}

view raw Sqrt.java hosted with ❤ by GitHub