python二分查找
时间: 2023-06-29 07:18:38 浏览: 60
二分查找(Binary Search)是一种在有序数组中查找特定元素的搜索算法。查找过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则查找过程结束;如果中间元素小于要查找的元素,则在数组的右半部分继续查找;如果中间元素大于要查找的元素,则在数组的左半部分继续查找。重复以上步骤,直到找到要查找的元素或者查找范围为空。
以下是 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` 表示要查找的有序数组,`left` 表示数组的左边界,`right` 表示数组的右边界,`x` 表示要查找的元素。初始时,`left` 和 `right` 的值分别为数组的起始位置和结束位置。如果查找成功,则返回要查找的元素在数组中的位置;如果查找失败,则返回 `-1`。