[算法]二分查找

二分查找

二分查找的多种区间定义写法主要体现在初始边界设定、循环条件、区间更新方式的不同，这些差异决定了代码实现的核心逻辑。以下是常见写法的分类与详细解析：

一、标准二分查找的两种主流写法

1. 左闭右闭区间 [left, right]

• 核心逻辑：目标值在包含左右边界的闭区间内，left和right均可访问。
• 代码特点：
  • 初始化：left = 0, right = nums.length - 1；
  • 循环条件：while (left <= right)（允许left == right，此时区间仍有效）；
  • 边界更新：
    • nums[mid] > target → right = mid - 1；
    • nums[mid] < target → left = mid + 1；
  • 返回值：找到目标时直接返回mid，否则返回-1。

示例代码：

int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

2. 左闭右开区间 [left, right)

• 核心逻辑：右边界不可访问，目标值仅存在于左闭右开区间内。
• 代码特点：
  • 初始化：left = 0, right = nums.length；
  • 循环条件：while (left < right)（left == right时区间无效）；
  • 边界更新：
    • nums[mid] > target → right = mid；
    • nums[mid] < target → left = mid + 1；
  • 返回值：同上。

示例代码：

int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

二、变种写法与特殊场景

3. 开区间 (left, right)

• 核心逻辑：左右边界均不可访问，适用于需要更灵活的边界处理（如查找左右边界）。
• 代码特点：
  • 初始化：left = -1, right = nums.length；
  • 循环条件：while (left + 1 < right)（确保区间内至少有两个元素）；
  • 边界更新：
    • nums[mid] < target → left = mid；
    • nums[mid] >= target → right = mid；
  • 返回值：通常返回right，即第一个大于等于目标的索引。

示例代码（查找左边界）：

int leftBound(int[] nums, int target) {
    int left = -1, right = nums.length;
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid;
        }
    }
    return (right < nums.length && nums[right] == target) ? right : -1;
}

4. 左开右闭区间 (left, right]

• 应用场景：较少见，通常结合具体问题调整（如旋转数组查找极值）。
• 代码特点：
  • 初始化：left = -1, right = nums.length - 1；
  • 循环条件：while (left < right)；
  • 边界更新：需根据问题逻辑调整，例如寻找最后一个目标值时更新right = mid。

三、关键区别与选择建议

四、常见误区与注意事项

1. 循环条件与区间定义需一致：例如左闭右闭必须使用left <= right，否则可能漏判边界值。
2. 防止整数溢出：计算mid时应使用mid = left + (right - left) / 2而非(left + right) / 2。
3. 重复元素的处理：当数组存在重复元素时，需通过调整边界逻辑寻找左/右边界。
4. 开闭区间的转换：例如左闭右开转换为左闭右闭时，需调整right初始值和更新逻辑。

五、综合应用示例

以LeetCode 34题（在排序数组中查找元素的第一个和最后一个位置）为例：

1. 左闭右开找左边界：通过不断压缩右边界确定第一个目标值的索引。
2. 左闭右闭找右边界：通过不断压缩左边界确定最后一个目标值的索引。

通过灵活选择区间定义，可以适应不同场景的二分查找需求。建议在编码时严格遵循所选区间的定义，并通过测试用例验证边界条件。

二分查找的不同区间写法（如左闭右闭、左闭右开）主要区别在于初始边界定义、循环终止条件和边界更新逻辑。以下是理解与记忆这些写法的关键要点：

一、核心记忆逻辑

1. 区间定义决定一切

• 左闭右闭 [left, right]：

  • 初始化：left = 0, right = nums.length - 1（覆盖所有元素）。
  • 循环条件：while (left <= right)（允许 left == right，此时区间仍有效）。
  • 边界更新：
    • nums[mid] > target → right = mid - 1（排除mid及其右侧）。
    • nums[mid] < target → left = mid + 1（排除mid及其左侧）。
  • 适用场景：标准查找、确定元素是否存在。

• 左闭右开 [left, right)：

  • 初始化：left = 0, right = nums.length（right不可访问）。
  • 循环条件：while (left < right)（left == right时区间无效）。
  • 边界更新：
    • nums[mid] > target → right = mid（排除mid及其右侧）。
    • nums[mid] < target → left = mid + 1（排除mid及其左侧）。
  • 适用场景：查找边界、避免重复元素处理。

2. 口诀记忆法

• 左闭右闭：
  “双闭包，可相等；right初始少一位，循环必须带等号，边界更新要减一。”
• 左闭右开：
  “右开不取尾，循环无等号；right初始总长度，边界更新用mid。”

二、对比表格辅助记忆

三、理解本质：区间收缩的一致性

1. 区间定义是核心：
   无论哪种写法，始终保持搜索区间的一致性。例如：

   • 左闭右闭的 right = mid - 1 是为了排除mid，确保新区间仍是闭区间。
   • 左闭右开的 right = mid 是为了保证新区间右端仍不可访问。

2. 防溢出技巧通用：
   计算中点时统一使用 mid = left + (right - left) / 2，避免 (left + right) 溢出。

3. 循环终止条件与区间有效性：

   • 左闭右闭的 left <= right 对应区间非空。
   • 左闭右开的 left < right 对应区间存在未检查元素。

四、常见误区与避坑指南

1. 混用区间定义：
   例如在左闭右闭中错误使用 right = mid，或在左闭右开中误用 right = mid - 1，会导致死循环或漏判。

2. 忽略整数溢出：
   未使用 mid = left + (right - left) / 2 而直接写 (left + right) / 2，可能在极端情况下溢出。

3. 边界条件测试不足：
   对空数组、单元素数组、全相同元素的数组进行测试，验证代码鲁棒性。

五、实战记忆步骤

1. 明确区间定义：选择一种写法（推荐左闭右闭，更直观）。
2. 死记初始化与循环条件：例如左闭右闭必用 right = length-1 和 <=。
3. 推导边界更新逻辑：根据区间定义，排除已检查的mid。
4. 用经典题验证：
   • LeetCode 704（标准查找）。
   • LeetCode 34（查找左右边界）。

通过理解区间定义的本质差异，结合口诀和对比表格，可以系统掌握二分查找的多种写法。建议选择一种写法并坚持使用，通过大量练习形成肌肉记忆。