写一段利用二分法查找的python代码
时间: 2023-05-23 22:05:51 浏览: 68
以下是一个利用二分法查找一个有序列表中某个元素的Python代码:
```
def binary_search(arr, x):
# 确定初始搜索范围
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
# 如果找到了目标元素,返回其所在位置
if arr[mid] == x:
return mid
# 如果目标元素比中间的元素大,更新左边搜索范围的起始元素
elif arr[mid] < x:
left = mid + 1
# 如果目标元素比中间的元素小,更新右边搜索范围的结束元素
else:
right = mid - 1
# 如果没有找到目标元素,返回 -1
return -1
```
这个函数输入一个有序列表 `arr` 和要查找的元素 `x`,返回 `x` 在列表中的位置。如果 `x` 不在列表中,返回 `-1`。二分法搜索算法的时间复杂度为 `O(logn)`,因此在大型列表中查找效率非常高。
相关问题
用python写一段二分法查找的程序
以下是用 Python 写的一个简单的二分法查找程序:
```python
def binary_search(arr, x):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid - 1
else:
return mid
return -1
arr = [2, 4, 7, 9, 12, 15, 19, 21]
x = 15
result = binary_search(arr, x)
if result != -1:
print(f"元素在索引 {result} 处")
else:
print("元素不在数组中")
```
在这个程序中,我们定义了一个名为 `binary_search` 的函数,它接受两个参数:`arr` 表示要查找的数组,`x` 表示要查找的元素。函数使用一个 while 循环来执行二分查找,每次迭代都将数组分成两部分,然后根据中间元素与要查找的元素的大小关系缩小查找范围。如果找到了要查找的元素,函数会返回它的索引;否则,函数会返回 -1。在主程序中,我们定义了一个数组和要查找的元素,然后调用 `binary_search` 函数来查找它们。如果找到了元素,程序会输出它的索引;否则,程序会输出“元素不在数组中”。
用python写一段代码 要求用二分法求5的平方根
当然,我可以帮您完成这个问题,请参考以下代码:
```
def sqrt(num):
# 设置上限和下限
low, high = 0, num
# 二分查找
while low <= high:
mid = (low + high) / 2
if mid * mid == num:
return mid
elif mid * mid < num:
low = mid + 1
else:
high = mid - 1
# 如果没有找到,返回-1
return -1
print(sqrt(5))
```
该代码使用了二分法的思想,不断缩小查找区间,最终可以找到5的平方根。