sqrt

public class Solution{
	public int sqrt(int x) {
        // write your code here

        if(x == 0) return 0;

        //find a number s which make s^2 <=x which is the last position of a target
        //00000000[0]xxxxxxxxxx
        //start from 1, end x
        //in order to avoid int overflow, use x divide mid instead of mid * mid. for example,
        //mid is very large and mid * mid may larger than int capacity
        int start = 1, end = x;
        while(start + 1 < end){
        	int mid = start + (end - start)/2;

        	if (x/mid == mid) {
        		return mid;
        	}
        	else if(x/mid >  mid){
        		start = mid;
        	}else{
        		end = mid;
        	}
        }
        
        
        if (x / end >= end) {
        	return end;
        }else{
        	return start;
        }
    }
}