Python搜索算法——二分搜索

二分搜索算法（Binary Search）是一种高效的搜索算法，用于在有序数组中查找目标元素。它通过反复将目标值与数组的中间元素进行比较，并根据比较结果缩小搜索范围，直到找到目标值或确定它不在数组中。

二分搜索算法步骤：

1. 初始化左右指针，分别指向数组的起始和结束位置。
2. 在每一步中，计算中间元素的索引，然后获取中间元素的值。
3. 将目标值与中间元素的值进行比较。
   • 如果目标值等于中间元素的值，则找到目标元素，返回其索引。
   • 如果目标值小于中间元素的值，则在左半部分继续搜索。
   • 如果目标值大于中间元素的值，则在右半部分继续搜索。
4. 重复上述步骤，直到找到目标元素或左右指针相遇（表示目标元素不在数组中）。

二分搜索算法示例实现：

def binary_search(arr, target):
    """
    在有序数组中进行二分搜索，并返回目标元素的索引（如果找到）。
    
    Parameters:
        arr (list): 有序数组。
        target: 要搜索的目标元素。
    
    Returns:
        int: 目标元素的索引，如果找到；否则返回-1。
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

# 示例数组
arr = [2, 4, 6, 8, 10, 12, 14]
# 目标元素
target = 10

# 进行二分搜索
index = binary_search(arr, target)
if index != -1:
    print(f"目标元素 {target} 在数组中的索引为 {index}")
else:
    print(f"数组中未找到目标元素 {target}")

以上是二分搜索算法的实现示例。

由于二分搜索算法每次都将搜索范围减半，因此其时间复杂度为O(logn)，其中n是数组的长度。这使得二分搜索算法在大规模有序数组中查找目标元素时非常高效。