本篇内容将深入探讨二分查找算法，特别针对 LeetCode 第 704 题进行讲解。

LeetCode 704 题：二分查找

题目描述

给定一个已排序（升序）的整数数组 nums，其中包含 n 个元素，以及一个目标值 target。编写一个函数来搜索 nums 中的 target。如果 target 存在，则返回其索引；否则，返回 -1。

示例 1：

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2：

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

题目提示：

• 可以假设 nums 中的所有元素是互不相同的。
• 数组 nums 的长度 n 的范围为 [1, 10000]。
• nums 中的每个元素的值范围为 [-9999, 9999]。

二分查找算法核心原理

二分查找算法的应用前提是 **数组必须是有序的**，且题目中强调 **数组元素无重复**。如果存在重复元素，二分查找返回的索引可能不是唯一的。这两个条件是应用二分查找的关键。

二分查找涉及较多的边界条件，虽然逻辑看似简单，但在实际编写时容易出错。常见的问题包括：循环条件是 while (left < right) 还是 while (left <= right)？以及边界更新是 right = middle 还是 right = middle - 1？

导致这些困惑的主要原因是对 **搜索区间的定义** 没有清晰理解。在二分查找过程中，**区间的定义应保持不变（不变量）**。每次边界处理都应遵循这个定义，这便是"循环不变量"原则。

在二分查找中，区间的定义通常有两种：

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

下面将分别介绍这两种区间定义下的二分查找实现方式。

二分查找的两种实现方式

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

当我们将目标值 target 定义在一个左闭右闭的区间 [left, right] 内时，代码实现需要遵循以下两点：

• 循环条件应使用 while (left <= right)。因为当 left == right 时，区间仍然有效，可能包含目标元素。
• 如果 nums[middle] > target，则将 right 更新为 middle - 1。这是因为当前 nums[middle] 必定不是 target，因此下一个搜索区间的右边界应设为 middle - 1。

代码示例：

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; // 右边界为数组最后一个元素的索引

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

            if (nums[mid] == target) {
                return mid; // 找到目标，返回索引
            } else if (nums[mid] < target) {
                left = mid + 1; // 目标在右侧，更新左边界
            } else { // nums[mid] > target
                right = mid - 1; // 目标在左侧，更新右边界 (nums[mid] 不可能是目标)
            }
        }

        return -1; // 目标不存在
    }
}

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

当我们将目标值 target 定义在一个左闭右开的区间 [left, right) 内时，二分查找的边界处理方式会有所不同：

• 循环条件应使用 while (left < right)。因为当 left == right 时，区间 [left, right) 为空，没有意义。
• 如果 nums[middle] > target，则将 right 更新为 middle。此时 nums[middle] 不等于 target，需要去左侧区间继续查找。由于区间是左闭右开的，下一个搜索区间的右边界设置为 middle，意味着 nums[middle] 不会被再次比较。

代码示例：

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length; // 右边界为数组长度，表示开区间

        while (left < right) { // 当 left == right 时，区间为空
            int mid = left + (right - left) / 2; // 防止整型溢出

            if (nums[mid] == target) {
                return mid; // 找到目标，返回索引
            } else if (nums[mid] < target) {
                left = mid + 1; // 目标在右侧，更新左边界
            } else { // nums[mid] > target
                right = mid; // 目标在左侧，更新右边界 (nums[mid] 不再考虑)
            }
        }

        return -1; // 目标不存在
    }
}

总结

二分查找的关键在于清晰地理解和一致地维护 **搜索区间的定义**。在循环过程中，始终根据预设的区间定义来处理边界条件，是遵循"循环不变量"原则的表现。

本文通过介绍两种常见的区间定义（左闭右闭和左闭右开），详细阐述了它们对应的二分查找实现方式，并解释了每一步边界处理的原因。