binary_search：在有序列表中查找特定元素的位置

二分查找，也称折半查找，是一种在有序列表中查找某一特定元素的搜索算法。它的基本思想是：将有序列表按照中间元素分为两个子序列，如果中间元素等于要查找的元素，则查找成功；否则，如果中间元素大于要查找的元素，则在左侧子序列中继续查找；如果中间元素小于要查找的元素，则在右侧子序列中继续查找。

二分查找的时间复杂度为 O(log n)，即每一次查找都将待查找元素的查找范围缩小一半。这种查找算法适用于数据量较大、数据项较多的有序列表中。在实际应用中，二分查找的效率比顺序查找、哈希查找等算法高得多。

二分查找的步骤如下：

1. 初始化left和right分别为0和n-1，其中n为列表长度。

2. 计算中间位置mid = (left + right) / 2，取整。如果mid位置的元素等于要查找的元素，则查找成功，返回mid位置。

3. 如果mid位置的元素大于要查找的元素，则在left到mid-1之间继续查找；如果mid位置的元素小于要查找的元素，则在mid+1到right之间继续查找。

4. 如果查找范围缩小到左右指针相等时仍然没有找到要查找的元素，则查找失败，返回-1。

以下是二分查找的Python实现示例：

def binary_search(arr, x):
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
            right = mid - 1
        else:
            left = mid + 1
    return -1

在实际应用中，二分查找可以结合递归算法来实现。例如，以下是使用递归算法实现二分查找的Python示例：

def binary_search(arr, x, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == x:
        return mid
    elif arr[mid] > x:
        return binary_search(arr, x, left, mid - 1)
    else:
        return binary_search(arr, x, mid + 1, right)

二分查找的优点是可以快速定位要查找的元素，只需要比较log n次。然而，二分查找仅适用于有序列表，如果列表未排序，则需要先排好序再进行查找。此外，如果列表长度过小，则顺序查找可能比二分查找更快。