二分查找（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`。函数返回找到的元素的下标，如果元素不存在，则返回一个指示元素未找到的消息。
需要注意的是，二分查找要求列表是有序的，否则算法无法正确工作。