2025-05-28 Python-List-二分法-EW帮帮网

Python数组在内存中的存储方式

在Python中，数组（列表）是一种常用的数据结构。它在内存中的存储方式具有以下特点：

一、连续存储

Python数组中的元素在内存中是连续存储的。这意味着数组中的元素在内存中是一个挨着一个存放的。
例如，对于一个包含整数的数组 [1, 2, 3, 4, 5] ，这些整数在内存中是依次排列的。

二、动态大小

Python数组具有动态大小的特性。这意味着可以在运行时根据需要增加或减少数组的大小。
当向数组中添加元素时，如果数组已满，Python会自动分配更多的内存空间来容纳新元素。
例如，当向一个已满的数组中添加一个新元素时，Python会重新分配一块更大的内存空间，将原数组中的元素复制到新的内存空间中，并添加新元素。

三、引用计数

Python使用引用计数来管理内存。每个对象都有一个引用计数，用于记录有多少个变量引用该对象。
当一个对象的引用计数为0时，Python会自动回收该对象所占用的内存空间。
对于数组中的元素，Python会为每个元素维护一个引用计数。当一个元素的引用计数为0时，Python会自动回收该元素所占用的内存空间。

四、内存管理

Python的内存管理是自动进行的。Python会自动分配和回收内存，程序员不需要手动管理内存。
当创建一个数组时，Python会自动分配足够的内存空间来容纳数组中的元素。
当数组不再使用时，Python会自动回收数组所占用的内存空间。

五、核心思想

前提条件：有序结构

二分查找通过不断将区间 [left, right] 二分，排除掉一半不可能包含目标值的部分，在对数时间内定位目标元素或其边界。

时间复杂度：$O(\log n)$
空间复杂度：$O(1)$（递归为 $O(\log n)$）
特征：单调性是可二分的关键

六、基本实现（闭区间 vs 半开区间）

1. 闭区间写法（推荐）

def binary_search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1  # 闭区间 [left, right]
    while left <= right:
        mid = left + (right - left) // 2  # 防止溢出
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

容易扩展成上/下边界查找
不容易漏掉边界值

七、可视化理解：有序区间的收缩

目标值：7      nums = [1, 3, 4, 6, 7, 8, 9]
              l        m        r
                -> 缩小区间到包含目标的一半

四、常见变种（边界问题）


类型	目标描述	条件	返回值
标准查找	找到等于 target 的位置	nums[mid] == target	返回任意一个匹配的索引
下界（Lower Bound）	第一个 ≥ target 的位置	nums[mid] >= target	可用于插入位置
上界（Upper Bound）	第一个 > target 的位置	nums[mid] > target	类似 C++ STL 中的 upper_bound
最后一个 ≤ target	类似下界的反向逻辑	nums[mid] <= target	适用于分段边界

五、工程应用中的二分法抽象

通用模型

如果存在一个布尔函数 f(x) ，其值关于 x 单调（如 False False ... True True ），那么可以用二分找到第一个为 True 的点：

def binary_search_predicate(f, left, right):
    while left < right:
        mid = (left + right) // 2
        if f(mid):
            right = mid
        else:
            left = mid + 1
    return left

七、典型使用场景


场景	描述
有序数组搜索	元素查找、边界查找
数值解法	二分答案，例如最大值最小化、最小可行解
凸函数优化	unimodal 函数上找最值（即三分法）
单调函数决策	如「是否可行」的布尔判断结构
分段函数跳转	例如段树、跳表中的查找路径

八、二分答案

当无法直接查找目标值时，可以转化为：

❝ 将结果视作单调函数的输入，对结果空间进行二分 ❞

示例：最小化最大工作量

def is_feasible(limit):
    # 检查是否在限制下可行
    ...

low, high = 0, 10**9
while low < high:
    mid = (low + high) // 2
    if is_feasible(mid):
        high = mid
    else:
        low = mid + 1

2025-05-28 Python-List-二分法