Sqrt(x) @leetcode

Sqrt.java

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;
	}
}