2025-05-28 Python-List-二分法
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 midelif nums[mid] < target:left = mid + 1else:right = mid - 1return -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) // 2if f(mid):right = midelse:left = mid + 1return left
七、典型使用场景
| 场景 | 描述 |
| 有序数组搜索 | 元素查找、边界查找 |
| 数值解法 | 二分答案，例如最大值最小化、最小可行解 |
| 凸函数优化 | unimodal 函数上找最值（即三分法） |
| 单调函数决策 | 如「是否可行」的布尔判断结构 |
| 分段函数跳转 | 例如段树、跳表中的查找路径 |
八、二分答案
当无法直接查找目标值时，可以转化为：
❝ 将结果视作单调函数的输入，对结果空间进行二分 ❞
示例：最小化最大工作量
def is_feasible(limit):# 检查是否在限制下可行...low, high = 0, 10**9
while low < high:mid = (low + high) // 2if is_feasible(mid):high = midelse:low = mid + 1