二分查找 Python
时间: 2023-03-28 19:01:18 浏览: 78
二分查找是一种常用的查找算法,可以在有序数组中快速查找指定元素。在 Python 中,可以使用 bisect 模块来实现二分查找。具体实现方法可以参考以下代码:
```python
import bisect
def binary_search(arr, x):
i = bisect.bisect_left(arr, x)
if i != len(arr) and arr[i] == x:
return i
else:
return -1
```
其中,arr 表示有序数组,x 表示要查找的元素。函数返回元素在数组中的下标,如果不存在则返回 -1。
相关问题
二分查找 python
二分查找(Binary Search)是一种在有序数组中查找指定元素的算法。它通过将目标值与数组的中间元素进行比较,从而缩小查找范围,直到找到目标值或确定目标值不存在。
以下是一个使用Python实现的二分查找的示例代码:
```python
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
# 测试
arr = [1, 3, 5, 7, 9]
target = 5
result = binary_search(arr, target)
if result != -1:
print("元素在索引", result, "处找到")
else:
print("元素不在数组中")
```
该代码首先初始化一个低位和高位指针,然后在循环中计算中间元素的索引。如果中间元素等于目标值,就返回该索引;如果中间元素小于目标值,就将低位指针移到中间元素的下一个位置;如果中间元素大于目标值,就将高位指针移到中间元素的上一个位置。重复这个过程直到找到目标值或者确定目标值不存在。
以上是二分查找的基本实现,你可以根据具体需求进行适当的修改和扩展。希望能对你有所帮助!如有更多问题,请继续提问。
二分查找python
二分查找(Binary Search)是一种常用的查找算法。它适用于已排序的数组或列表。下面是一个用Python实现二分查找的示例代码:
```python
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
# 示例使用
arr = [1, 3, 5, 7, 9]
target = 5
result = binary_search(arr, target)
if result != -1:
print("元素在索引", result)
else:
print("元素不在数组中")
```
这段代码定义了一个 `binary_search` 函数,它接受一个已排序的数组 `arr` 和目标值 `target`。算法使用两个指针 `low` 和 `high` 分别表示当前查找范围的最低索引和最高索引。在每一次迭代中,算法计算中间索引 `mid`,并将目标值与中间元素进行比较。如果目标值等于中间元素,则返回该索引;如果目标值小于中间元素,则将最高索引更新为中间索引减一;如果目标值大于中间元素,则将最低索引更新为中间索引加一。如果循环结束后仍未找到目标值,则返回 -1。
在示例中,我们创建了一个已排序的数组 `[1, 3, 5, 7, 9]`,并且要查找的目标值是 `5`。调用 `binary_search` 函数后,返回索引 2,表示目标值在数组中的位置。
希望这个示例对你有帮助!如果你还有其他问题,请继续提问。