二分查找（Binary Search）是一种在有序列表中查找特定素的搜索算法。其核心思想是每次比较列表中间素与目标值，根据比较结果缩小搜索范围至原来的一半，重复此过程直到找到目标值或搜索范围为空。
1. 确定列表的中间位置。
2. 将中间位置的素与目标值进行比较。
3. 如果中间素等于目标值，则查找成功，返回中间位置的下标。
4. 如果中间素小于目标值，则在列表的右半部分继续查找。
5. 如果中间素大于目标值，则在列表的左半部分继续查找。
6. 重复步骤1至5，直到找到目标值或搜索范围为空。
二分查找的时间复杂度为 O（log n），其中 n 是列表中素的数量，因为它每次都将搜索范围减半。
在Python中实现二分查找，通常需要一个递归函数，如下所示：
def binary_search（arr, left, right, x）:if left <= right:mid = （left + right） // 2if arr[mid] == x:return midelif arr[mid] < x:return binary_search（arr, mid + 1, right, x）else:return binary_search（arr, left, mid - 1, x）else:return "Element is not present in array"
这段代码定义了一个名为 `binary_search` 的函数，它接受一个有序列表 `arr`、搜索范围的左右边界 `left` 和 `right`，以及要查找的素 `x`。函数返回找到的素的下标，如果素不存在，则返回一个指示素未找到的消息。
需要注意的是，二分查找要求列表是有序的，否则算法无法正确工作。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://sigusoft.com/bj/93850.html