用pyrhon写一个二分搜索,在递增数组中寻找特定元素
时间: 2023-04-02 11:00:53 浏览: 154
对数组进行二分查找
二分搜索是一种高效的查找算法,可以在递增数组中寻找特定元素。以下是用 Python 实现的二分搜索代码:
```
def binary_search(arr, target):
left, 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 表示递增数组,target 表示要查找的元素。算法的核心思想是不断缩小查找范围,直到找到目标元素或者查找范围为空。
具体实现中,我们使用两个指针 left 和 right 分别指向数组的左右两端,然后计算中间位置 mid。如果中间位置的元素等于目标元素,直接返回 mid;如果中间位置的元素小于目标元素,说明目标元素在右半部分,将 left 指针移到 mid+1 的位置;如果中间位置的元素大于目标元素,说明目标元素在左半部分,将 right 指针移到 mid-1 的位置。不断重复这个过程,直到找到目标元素或者查找范围为空。
如果找到目标元素,返回它的下标;否则返回 -1,表示没有找到。
阅读全文