python实现二分搜索算法
时间: 2023-07-07 13:10:54 浏览: 58
二分搜索算法,也称折半搜索,是一种在有序数组中查找某一特定元素的搜索算法。它的基本思想是,将数组中间位置的元素与目标值进行比较,如果相等,则返回索引;如果目标值小于中间元素,则在数组左半部分继续查找;如果目标值大于中间元素,则在数组右半部分继续查找。重复以上过程,直到找到目标值或者数组被遍历完。
以下是 Python 实现二分搜索算法的代码:
```python
def binary_search(arr, target):
left, right = 0, 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 是要查找的目标值。该函数返回目标值在数组中的索引,如果目标值不存在,则返回 -1。
实现过程中,首先定义左右两个指针,分别指向数组的起始位置和结束位置。然后在循环中计算中间位置 mid,并将其与目标值进行比较。如果相等,则返回 mid;如果目标值小于中间元素,则将右指针移动到 mid - 1 的位置,继续在左半部分查找;如果目标值大于中间元素,则将左指针移动到 mid + 1 的位置,继续在右半部分查找。重复以上步骤,直到找到目标值或者数组被遍历完。如果目标值不存在,则返回 -1。