public int sqrt2(int x) { // binary search solution
		long i = 0;
        long j = x/2+1;
		while(i <= j){
            long mid = (i+j)/2;
            System.out.println(i+ " " + j +  " " + mid + " " + mid*mid);
            long s = mid*mid;
			if(s == x) return (int)mid;
			if(s < x) i = mid+1;
			else j = mid - 1;
		}
        // tricky to return j
        return (int)j;
	}