用Python实现二分查找算法
时间: 2024-04-06 19:27:16 浏览: 36
二分查找算法是一种高效的查找算法,它适用于有序数组。下面是用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`是要进行查找的有序数组,`target`是要查找的目标元素。算法首先将数组的最低索引`low`设置为0,最高索引`high`设置为数组长度减1。然后,在每次循环中,计算中间索引`mid`,并将中间元素与目标元素进行比较。如果中间元素等于目标元素,则返回中间索引。如果中间元素小于目标元素,则将最低索引`low`更新为`mid + 1`,否则将最高索引`high`更新为`mid - 1`。循环继续直到找到目标元素或者最低索引大于最高索引。
如果找到目标元素,则返回其索引;如果未找到目标元素,则返回-1表示未找到。
相关问题
用python实现二分查找算法
二分查找也叫折半查找,它是一种效率较高的查找算法,前提是数据必须是有序的。其基本思想是:将n个元素分成大致相等的两部分,取中间值与待查关键字进行比较,如果中间值大于待查关键字,则在左半部分继续执行查找;如果中间值小于待查关键字,则在右半部分继续查找,直到查找成功或者查找结束。
下面是Python实现二分查找算法的代码:
```python
def binary_search(arr, left, right, x):
# 如果左指针大于右指针,说明查找失败
if left > right:
return -1
# 计算中间位置
mid = (left + right) // 2
# 如果中间位置的元素等于要查找的值,返回下标
if arr[mid] == x:
return mid
# 如果中间位置的元素大于要查找的值,继续在左侧查找
elif arr[mid] > x:
return binary_search(arr, left, mid - 1, x)
# 如果中间位置的元素小于要查找的值,继续在右侧查找
else:
return binary_search(arr, mid + 1, right, x)
# 测试
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
x = 5
result = binary_search(arr, 0, len(arr)-1, x)
if result != -1:
print("元素在数组中的下标为", str(result))
else:
print("元素不在数组中")
```
输出结果为:
```
元素在数组中的下标为 4
```
说明在有序数组 `[1, 2, 3, 4, 5, 6, 7, 8, 9]` 中查找元素 `5` 的下标是 `4`。
Python:实现二分查找算法
二分查找算法也称为折半查找算法,是一种高效的查找算法。它的基本思想是:在有序数组中,通过将数组不断地对半分,找到目标元素的位置。
以下是 Python 代码实现:
```python
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # 目标元素不存在
# 测试
arr = [1, 3, 5, 7, 9]
target = 5
print(binary_search(arr, target)) # 输出: 2
```
这里的 `arr` 表示有序数组,`target` 表示要查找的目标元素。`left` 和 `right` 分别表示数组的左边界和右边界。
在 `while` 循环中,我们计算出数组的中间位置 `mid`,如果 `arr[mid]` 等于 `target`,则直接返回 `mid`。如果 `arr[mid] < target`,则目标元素在右半部分,需要将左边界 `left` 赋值为 `mid + 1`。如果 `arr[mid] > target`,则目标元素在左半部分,需要将右边界 `right` 赋值为 `mid - 1`。如果 `while` 循环结束后仍然没有找到目标元素,则返回 `-1` 表示目标元素不存在。
以上是二分查找算法的 Python 实现。