数据结构折半查找代码
时间: 2023-02-06 10:59:34 浏览: 70
好的,这是一个使用折半查找算法在 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:
right = mid - 1
# 如果目标元素比中间元素大,则在右半部分查找
else:
left = mid + 1
# 如果没有找到目标元素,返回 -1
return -1
# 测试代码
arr = [1, 3, 5, 7, 9]
target = 5
index = binary_search(arr, target)
print(index) # 输出 2
```
折半查找是一种在有序数组中查找元素的高效算法。它的基本思想是,每次查找都将要查找的数组分成两半,并根据目标元素与数组中间元素的大小关系,将查找范围缩小一半。这样,每次查找的复杂度就降低了一半,导致总的查找复杂度大大降低。