Pythonic版二分查找的实现

当前位置:

首页 > Python基础教程 >

Pythonic版二分查找的实现

Pythonic 风格的二分查找实现通常会注重代码的简洁性、可读性和 Python 语言的特性。下面是一个使用 Python 实现的二分查找算法，它返回目标值在有序数组中的索引，如果目标值不存在则返回 -1。

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2 # 防止 (left + right) // 2 导致的整数溢出

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

# 示例用法
sorted_array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target_value = 7
result = binary_search(sorted_array, target_value)

if result != -1:
    print(f"目标值 {target_value} 在数组中的索引为: {result}")
else:
    print(f"目标值 {target_value} 不在数组中")

这个实现有几个关键点：

1. **变量命名**：`left` 和 `right` 分别表示搜索区间的左右边界，`mid` 表示当前区间的中点。这些命名都是直观且易于理解的。

2. **整数溢出**：在计算 `mid` 时，使用 `left + (right - left) // 2` 而不是 `(left + right) // 2`，这是为了防止在 `left` 和 `right` 都非常大的情况下发生整数溢出。

3. **循环条件**：使用 `while left <= right` 来确保搜索区间是有效的。当 `left` 大于 `right` 时，表示搜索区间为空，可以退出循环。

4. **返回值**：如果找到目标值，则返回其索引；如果未找到，则返回 -1，表示目标值不在数组中。

这个实现是 Pythonic 的，因为它简洁、易于理解，并且充分利用了 Python 的语言特性（如整数除法）。同时，它也遵循了二分查找算法的基本思想，具有 O(log n) 的时间复杂度。

最后，如果你对python语言还有任何疑问或者需要进一步的帮助，请访问https://www.xin3721.com 本站原创，转载请注明出处：
https://www.xin3721.com/Python/python50593.html

栏目列表