[Java][LeetCode][BinarySearch] Sqrt(X) #69

SP Hou
Jul 22, 2022

--

用二元搜尋找(猜)平方根,
用乘法:
乘法概念是比較容易理解的,但x的範圍是0~(2³²)-1,有機會在做了x的平方,會超過integer的範圍,所以要將這個部分的type用long (2⁶³-1)。
用除法:
商會落在int的範圍內,
x=n*n,n是x的平方根,所以n=x/n
product=mid*mid,mid是x的平方根,所以mid=product/mid
。x=mid*mid的時候,表示mid是x的平方根,直接return mid。
。x/mid>mid的時候,表示x>mid*mid,我要將mid*mid往上提升接近x,所以要將left移到mid,又因為知道mid*mid<x,可以肯定target會在mid的右側,所以將left移到mid+1。
。x/mid<mid的時候,表示x<mid*mid,我要將mid*mid往下修正接近x,所以要將right移到mid,又因為知道mid*mid>x,可以肯定target會在mid的左側,所以將right移到mid。
當left≥right的時候,結束while loop,
因為decimal digits are truncated且在最後一次left做了mid+1,所以輸出前要將left-1。

--

--