二分查找算法详解：闭区间与半开区间的实现与异同

什么是二分查找算法？

二分查找（Binary Search）是一种在有序数组中查找特定元素的高效算法。它的核心思想很简单，就像我们猜一个1到100之间的数字一样：

1. 你猜一个中间数，比如50。
2. 我告诉你”太大了”或”太小了”。
3. 如果太大了，你就知道答案在1到49之间；如果太小了，答案就在51到100之间。
4. 你不断地在新的、缩小的范围里重复猜中间数，直到找到答案。

这个过程将搜索范围一次性排除掉一半，所以效率非常高。其时间复杂度为 **O(log n)**，其中 n 是数组中元素的数量。相比于需要逐个检查的线性查找（O(n)），二分查找在数据量大时优势极其明显。

前提条件： 数组必须是已排序的。

为什么要注意区间的开闭？

这正是二分查找算法的精髓与难点所在，也是绝大多数人初次实现时会出错的地方。区间的定义（开或闭）直接决定了你的循环条件和边界更新逻辑。如果定义不清晰、逻辑不一致，就会导致死循环或者找不到存在的元素。

我们通常有两种定义区间的方式：

方式一：闭区间 [left, right]

这是最常见也最直观的写法。

• 区间定义：我们的目标是在 [left, right] 这个闭区间内寻找目标值 target。left 和 right 都是有效的数组索引。
• 循环条件：while (left <= right)。
  • 当 left == right 时，区间 [left, left] 仍然是有效的，里面有一个元素，需要检查。
  • 当 left > right 时，比如 left = 5, right = 4，区间 [5, 4] 已经无效了，说明没找到，循环终止。
• 边界更新：
  • 如果 nums[mid] > target，说明 target 在 mid 的左侧。因为 mid 已被检查过且不符合，所以新的搜索区间是 [left, mid - 1]。因此，right = mid - 1。
  • 如果 nums[mid] < target，说明 target 在 mid 的右侧。新的搜索区间是 [mid + 1, right]。因此，left = mid + 1。
  • 如果 nums[mid] == target，找到了，直接返回 mid。

代码示例（Java）：

public int search(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }

    int left = 0;
    int right = nums.length - 1; // [left, right]

    while (left <= right) { // 当区间有效时循环
        int mid = left + (right - left) / 2; // 防止溢出

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1; // target 在右侧，搜索 [mid + 1, right]
        } else { // nums[mid] > target
            right = mid - 1; // target 在左侧，搜索 [left, mid - 1]
        }
    }
    return -1; // 未找到
}

方式二：半开半闭区间 [left, right)

这种写法在C++ STL或Java的 Arrays.binarySearch 等标准库实现中很常见。

• 区间定义：我们的目标是在 [left, right) 这个区间内寻找 target。left 是有效的，但 right 是一个无效的边界，它指向目标区域的后一个位置。
• 循环条件：while (left < right)。
  • 当 left == right 时，比如 [5, 5)，区间为空，不包含任何元素，循环终止。
• 边界更新：
  • 如果 nums[mid] > target，说明 target 在 mid 的左侧。因为 right 本身是开区间（不被包含），所以新的搜索区间是 [left, mid)。因此，right = mid。
  • 如果 nums[mid] < target，说明 target 在 mid 的右侧。新的搜索区间是 [mid + 1, right)。因此，left = mid + 1。
  • 如果 nums[mid] == target，找到了，直接返回 mid。

代码示例（Java）：

public int search(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }

    int left = 0;
    int right = nums.length; // [left, right)

    while (left < right) { // 当区间不为空时循环
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1; // target 在右侧，搜索 [mid + 1, right)
        } else { // nums[mid] > target
            right = mid; // target 在左侧，搜索 [left, mid)
        }
    }
    return -1;
}

总结

特性	闭区间 [left, right]	半开区间 [left, right)
区间定义	left 和 right 都是有效索引	left有效，right是上界（无效）
初始值	right = nums.length - 1	right = nums.length
循环条件	while (left <= right)	while (left < right)
right更新	right = mid - 1	right = mid
left更新	left = mid + 1	left = mid + 1

核心要点： 你必须选择一种区间的定义，并严格遵守该定义下的所有逻辑（循环条件和边界更新）。一旦混用，比如用 while(left < right) 搭配 right = mid - 1，就极有可能在 target 恰好是边界值时错过它。

因此，在实现二分查找时，第一步就是**明确你的搜索区间是 [left, right] 还是 [left, right)**，然后围绕这个定义去书写代码。