CodeGym /课程 /Python SELF ZH /二分查找

二分查找

Python SELF ZH

第 53 级 , 课程 1

可用

2.1 二分查找的定义及其基本概念

二分查找 是一种在 已排序的数组中 查找元素的算法，其工作原理是将数组分成两半。这个算法比线性查找器对于大数组而言效率高得多，因为它通过在每次迭代中将数组分成两部分来减少检查的次数。

基本概念：

已排序数组： 二分查找仅适用于已排序的数组。
对半分： 算法将查找的元素与数组中的中间元素进行比较。
递归或迭代分割： 如果查找元素小于中间，继续在左半部分查找，否则就在右半部分查找。
结束条件： 当元素被找到或搜索范围为空时，搜索停止。

重要！二分查找需要已排序数组。

为了二分查找正常工作，输入数据必须 按升序排序。这是唯一的要求，因为算法基于数组元素有序这个事实。基于此，它可以在每次查找过程中有效地排除一半的元素。

已排序数组示例：


sorted_array = [1, 3, 5, 7, 9, 11, 13]

2.2 二分查找的逐步实现

二分查找的工作原理：

初始化： 设置初始搜索边界（数组的左边界和右边界）。
选择中间元素： 找到数组中间元素的索引。
比较： 将中间元素与目标值比较。
更新边界：
1. 如果中间元素等于目标值，返回它的索引。
2. 如果目标值小于中间元素，更新搜索的右边界。
3. 如果大于，更新左边界。
重复： 重复步骤2-4直到找到元素或者左边界大于右边界。

逐步算法：

初始化： 设定 left 为 0 和 right 为 len(arr) - 1。
计算中间元素： mid = (left + right) // 2
与目标元素比较：
1. 如果 arr[mid] == target，返回 mid
2. 如果 arr[mid] < target，更新 left = mid + 1
3. 如果 arr[mid] > target，更新 right = mid - 1
重复： 回到步骤2，直到 left <= right
如果元素未找到： 返回 -1

Python中二分查找的迭代实现：


def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (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, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"元素 {target} 找到在索引 {result}")  # 输出: 元素 7 找到在索引 3

2.3 二分查找的时间复杂度 `O(log n)`

二分查找的时间复杂度是 O(log n)，其中 n 是数组中的元素数量。这意味着在每一步中算法将元素数量减半，与线性查询的时间复杂度 O(n) 相比，这大大加快了速度。

时间复杂度分析：

最佳情况（Best case）： 在第一步中找到元素，O(1)。
平均情况（Average case）： O(log n)。
最坏情况（Worst case）： 在最后一步找到元素或不存在，O(log n)。

时间复杂度分析示例：


sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
index = binary_search(sorted_array, target)
print(f"元素 {target} 找到在索引 {index}")  # 输出: 元素 7 找到在索引 3

# 算法执行了3步（7个元素的对数）来寻找元素，
# 对应于 O(log n)

复杂性的图形表示：

想象一个包含16个元素的数组。