LeetCode-Sqrt(x)

Sqrt(x)

##题目

####Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

##解题思路
该题采用数值中经常用的另一种方法：二分法。基本思路是跟二分查找类似，要求是知道结果的范围，取定左界和右界，然后每次砍掉不满足条件的一半，直到左界和右界相遇。

比较典型的数值处理的题目还有Divide Two Integers，Pow(x,n)等，其实方法差不多，一般就是用二分法或者以2为基进行位处理的方法。

##算法代码
代码采用JAVA实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int sqrt(int x) {
        //知道结果的范围，可以采用二分法
        if(x<0)  return -1;
        if(x==0) return 0;
        int left=1;
        int right=x/2+1;
        while(left<=right)
        {
        	int m=(left+right)/2;
        	if(m<=x/m && (m+1)>x/(m+1))
        		return m;
        	if(m>x/m)
        		right=m-1;
        	else
        		left=m+1;
        }
        return 0;
    }
}

Comments

▲