python二分法求平方根b
时间: 2023-12-09 15:29:01 浏览: 85
可以使用二分法求平方根b的值,具体实现可以参考以下代码:
```python
def sqrt_bin_search(b):
if b < 0:
raise ValueError('Square root not defined for negative numbers')
if b == 0:
return 0
low, high = 0, b
while low <= high:
mid = (low + high) // 2
if mid * mid <= b < (mid + 1) * (mid + 1):
return mid
elif mid * mid > b:
high = mid - 1
else:
low = mid + 1
```
该代码使用了二分法来逼近平方根的值,通过比较mid和mid+1的平方与b的大小关系来确定平方根的值。注意,该算法的时间复杂度为O(log b)。
相关问题
Python二分法求平方根
二分法是一种常用的查找算法,可以用来在有序数组中查找特定元素。在这个问题中,我们可以使用二分法来求解平方根。具体步骤如下:
1. 定义left为0,right为传入的那个数字x。
2. 假定此时的mid:mid = (left + right) // 2。
3. 进行判断,若 mid * mid = x,则返回mid。
4. 若出现mid * mid > x的情况,则说明需要求的算术平方根在mid的左边,将right更新为mid-1。
5. 若出现mid * mid < x的情况,则说明需要求的算术平方根在mid的右边,将left更新为mid+1。
6. 重复步骤2-5,直到left>right,此时返回ans即可。
下面是Python代码实现:
```python
class Solution:
def mySqrt(self, x: int) -> int:
left = 0
right = x
ans = 0
while left <= right:
mid = (left + right) // 2
if mid * mid <= x:
left = mid + 1
ans = mid
else:
right = mid - 1
return ans
```
python用二分法求平方根B
可以使用以下代码来用二分法求平方根B:
```
def sqrt_binary_search(B):
if B==0 or B==1:
return B
left = 1
right = B
while left <= right:
mid = (left + right) // 2
if mid * mid == B:
return mid
elif mid * mid < B:
left = mid + 1
ans = mid
else:
right = mid - 1
return ans
```
其中,B是要求平方根的数,left 和 right 分别为左右两个边界,mid 为中间值,ans 是用来存储最终结果的变量。在每个循环中,我们都将mid与B比较,如果mid的平方等于B,那么mid就是B的平方根,直接返回即可。如果mid的平方小于B,说明B的平方根在mid的右边,我们将left 更新为mid+1,并将ans更新为mid。如果mid的平方大于B,说明B的平方根在mid的左边,我们将right更新为mid-1。直到left > right,最终答案是ans。