Reference: http://blog.csdn.net/lbyxiafei/article/details/9375735

?題目：

Implement int sqrt(int x).

Compute and return the square root of x.

?

題解：

這道題很巧妙的運用了二分查找法的特性，有序，查找pos（在這道題中pos=value），找到返回pos，找不到返回鄰近值。

因為是求數(shù)x（x>=0) 的平方根， 因此，結(jié)果一定是小于等于x且大于等于0，所以用二分查找法肯定能搜到結(jié)果。

?

以每一次的mid的平方來與target既數(shù)x相比：

如果mid*mid == x，返回mid；

如果mid*mid < x，那么說明mid過小，應讓low = mid+1，在右邊繼續(xù)查找

如果mid*mid > x，那么說明mid過大，應讓high = mid-1，在左邊繼續(xù)查找

若x無法開整數(shù)根號（在上述查找中沒有找到），那么我們?nèi)匀豢梢岳弥皩Χ植檎曳偨Y(jié)的技巧，當target值不在數(shù)組中，low指向大于target的那個值，high指向小于target的那個值，由于我們需要向下取整的結(jié)果，所以我們返回high指向的值（這里high指向的值和high的值是同一個值），這個值就是所求得最接近起開根號結(jié)果的整數(shù)值。

?

因為leetcode的test case x=2147395599，在算mid*mid的時候造成溢出，所以mid不能使用int型來接，要使用long型防止溢出（Java中Integer型的范圍：-2147483648?到2147483648）

?代碼為：

?1?public?int?sqrt(int?x)?{
?2?????????int?low?=?0;
?3?????????int?high?=?x;
?4?????????while(low<=high){
?5?????????????long?mid?=?(long)(low?+?high)/2;
?6?????????????if(mid*mid?<?x)
?7?????????????????low?=?(int)mid?+?1;
?8?????????????else?if(mid*mid?>?x)
?9?????????????????high?=?(int)mid?-?1;
10?????????????else
11?????????????????return?(int)mid;
12?????????}
13?????????return high;
14?????}

總結(jié)

以上是生活随笔為你收集整理的Sqrt(int x) leetcode java的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。