详细见：leetcode.com/problems/sqrtx

Java Solution: github

package leetcode;

public class P069_Sqrtx {
	public static void main(String[] args) {
		System.out.println(new Solution2().mySqrt(2147395599));
	}
	/*
	 * 	hehe
	 * 	2 ms
	 */
	static class Solution {
	    public int mySqrt(int x) {
	        return (int)Math.sqrt(x);
	    }
	}
	/*
	 * 	7 = 111b
	 * 	分为两步： 	1，100b
	 * 			  	2, 10b - 100b
	 * 	97 = 1100001b
	 * 	分为两步:	1，1100001b
	 * 				2，1000000b
	 * 				3，1000b - 10000b
	 * 	其实复杂度还是挺高的，应该算在O(N^0.5)
	 * 	4 ms
	 */
	static class Solution2 {
	    public int mySqrt(int x) {
	    	if (x == 1 || x == 0)
	    		return x;
	        int firstOne = 30;
	        while ((x >> firstOne --) != 1) {}
	        firstOne = (firstOne + 1) >> 1;
	        return binarySearch(x, 1 << firstOne, 1 << (firstOne + 1));
	    }
	    private int binarySearch(int x, int start, int end) {
	    	while (start < end) {
	    		int mid = ((start + end) & 0x1) == 1 ? ((start + end) >> 1) + 1 : (start + end) >> 1;
	        	long multi = ((long)mid) * mid;
	    		if (multi < x) {
	    			start = mid;
	    		} else if (multi > x) {
	    			end = mid - 1;
	    		} else {
	    			return mid;
	    		}
	    	}
	    	return start;
	    }
	}
}

C Solution: github

/*
    url: leetcode.com/problems/sqrtx
    mySqrt: AC 3ms 46.59%
    mySqrt2: AC 3ms 46.59%
*/

#include <math.h>
#include <stdio.h>
#include <stdlib.h>


int mySqrt(int x) {
    return (int) sqrt(x);
}

int cmp2(int sqrt_val, int x) {
    int val = sqrt_val * sqrt_val;
    if (val < 0) return 1;
    if (val < x) return -1;
    if (val > x) return 1;
    return 0;
}

int mySqrt2(int x) {
    int bit_1 = 0, xc = x;
    int sqrt_min = 0, sqrt_max = 0;
    int sqrt_mid = 0;
    
    if (x == 0) return 0;

    while (xc != 0) {
        bit_1 ++;
        xc = xc >> 1;
    }
    
    sqrt_max = 1 << ((bit_1+1) / 2);
    sqrt_min = 1 << ((bit_1-1) / 2);

    while (sqrt_min < sqrt_max) {
        sqrt_mid = (sqrt_max + sqrt_min) / 2;
        if (cmp2(sqrt_mid, x) <= 0) {
            if (cmp2(sqrt_mid+1, x) > 0)
                return sqrt_mid;
            sqrt_min = sqrt_mid + 1;
        } else {
            sqrt_max = sqrt_mid - 1;
        }
    }
    return sqrt_min;
}

int main() {
    printf("answer is %d\r\n", mySqrt2(2147395599));
    return 0;
}

Python Solution: github

#coding=utf-8

'''
    url: leetcode.com/problems/sqrtx/
    @author:     zxwtry
    @email:      zxwtry@qq.com
    @date:       2017年4月15日
    @details:    Solution: 56ms 55.71%
    @details:    Solution: 59ms 45.65%
'''
from math import sqrt

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        return int(sqrt(x))
    
class Solution2(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        n, xx = 0, x
        while xx != 0:
            xx, n = xx // 2, n+1
        if n < 2: return x
        sqrt_max = 1 << (n // 2 + 1)
        sqrt_min = 1 << (n // 2 - 1)
#        print("%d %d" %(sqrt_max, sqrt_min))
        sqrt_mid = 0
        while sqrt_min < sqrt_max:
            sqrt_mid = (sqrt_max + sqrt_min+1) // 2
            val = sqrt_mid * sqrt_mid
            if val < x:
                sqrt_min = sqrt_mid
            elif val == x:
                return sqrt_mid
            else:
                sqrt_max = sqrt_mid - 1
        return sqrt_min
    
if __name__ == "__main__":
    print(Solution2().mySqrt(1))