二分查找越界问题的核心认知
越界的常见表现
在实现二分查找时，最容易发生的越界是访问 mid 周围的元素时的下标越界。越界的表现通常体现在 critical错误，如 IndexError、segmentation fault，或者逻辑上返回错误的结果。
另外一个层面是循环条件不当导致的死循环或无限循环，死循环与越界往往同根，因为无效的边界更新会让 mid 越界之外的区域被重复访问。
要理解问题，应把握一个核心概念：边界的定义决定了循环是否收敛，因此选择左闭右闭、左开右闭或完全开区间都会直接影响越界风险。
越界的根本原因
常见原因包括未正确处理 when target 不在数组中的情况，未利用 低位和高位的边界条件不变量，以及 mid 的计算溢出风险（在极端大规模数据下需要注意）。
另一个常见源头是更新边界的代码顺序错误，例如先更新边界再计算 mid，导致本轮使用的 mid 已不在有效区间。先计算 mid，再根据比较结果更新边界是基本原则。
为避免此类问题，可以将边界设定为 low <= high 的左闭右闭区间，并在每次循环中严格保持不变式。
完整边界条件处理策略
区间定义与选择
选择区间的方式直接决定是否会产生越界。左闭右闭区间在大多数语言实现中更容易管理，因为高位始终有一个有效下标可比较。
另一种思路是使用 左开右闭区间，此时边界更新略有不同，但同样需要在循环退出条件处保持一致性。
循环条件与边界更新
核心规则是：while left <= right，在循环内部先计算 mid，再根据目标与 nums[mid] 的关系更新 left 或 right。
下面提供一个关键示例，展示在循环中的边界更新顺序：先判断相等情况再更新边界，确保 mid 不会重复进入已经排除的区间。
def binary_search(nums, target):left, right = 0, len(nums) - 1while left <= right:mid = left + (right - left) // 2if nums[mid] == target:return midelif nums[mid] < target:left = mid + 1else:right = mid - 1return -1
int binary_search(const vector& a, int target) {int l = 0, r = (int)a.size() - 1;while (l <= r) {int m = l + (r - l) / 2;if (a[m] == target) return m;if (a[m] < target) l = m + 1;else r = m - 1;}return -1;
}
代码实现要点与示例
迭代实现的关键点
在迭代实现中，避免 mid 越界的关键是正确的 mid 计算和边界更新，以及在访问 nums[mid] 之前确保 left <= right 为真。
另外，处理重复元素时需要考虑返回第一个出现的位置或任意位置的需求。下面的示例展示了在有序数组中查找目标的常用模式。边界条件设计要点贯穿整个实现，以确保在极端情况下也不会越界。
本段落强调的要点，是实现稳健的边界条件时不可忽视的基础原则。
def binary_search_full(nums, target):left, right = 0, len(nums) - 1while left <= right:mid = left + (right - left) // 2cur = nums[mid]if cur == target:return midif cur < target:left = mid + 1else:right = mid - 1return -1
int binary_search_full(const vector& nums, int target) {int l = 0, r = (int)nums.size() - 1;while (l <= r) {int m = l + (r - l) / 2;if (nums[m] == target) return m;if (nums[m] < target) l = m + 1;else r = m - 1;}return -1;
}
递归实现的注意点
递归实现天然带来栈深度风险，但在边界处理上同样需要清晰的不变量。递归边界条件通常是区间的左边界和右边界之间的关系，以及返回值的边界意义。
递归实现需要小心：在每次调用前确保 mid 的计算不会越界，同时对等于目标的情况处理要尽快返回，以避免不必要的重复计算。下面给出递归版的核心框架。
def binary_search_recursive(nums, target, left, right):if left > right:return -1mid = left + (right - left) // 2if nums[mid] == target:return midif nums[mid] < target:return binary_search_recursive(nums, target, mid+1, right)else:return binary_search_recursive(nums, target, left, mid-1)
int binary_search_recursive(const vector& a, int target, int left, int right) {if (left > right) return -1;int mid = left + (right - left) / 2;if (a[mid] == target) return mid;if (a[mid] < target) return binary_search_recursive(a, target, mid+1, right);return binary_search_recursive(a, target, left, mid-1);
}
完整示例：处理升序数组的二分查找
下面给出一个完整示例，展示如何在升序数组中对目标值进行查找，同时确保边界条件处理的正确性。示例代码将展示边界初始化、mid 计算以及四种比较情况的边界更新。
def binary_search_full(nums, target):left, right = 0, len(nums) - 1while left <= right:mid = left + (right - left) // 2cur = nums[mid]if cur == target:return midif cur < target:left = mid + 1else:right = mid - 1return -1
int binary_search_full(const vector& nums, int target) {int l = 0, r = (int)nums.size() - 1;while (l <= r) {int m = l + (r - l) / 2;if (nums[m] == target) return m;if (nums[m] < target) l = m + 1;else r = m - 1;}return -1;
}
