public class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;  // 右边界包含在搜索区间内

        while (left <= right) {  // 当区间不为空时继续搜索
            int mid = left + (right - left) / 2;  // 防止整数溢出

            if (nums[mid] == target) {
                return mid;  // 找到目标，直接返回
            } else if (nums[mid] > target) {
                right = mid - 1;  // mid 已经排除，右边界左移
            } else {
                left = mid + 1;  // mid 已经排除，左边界右移
            }
        }

        return -1;  // 搜索区间为空，未找到目标
    }
}

复杂度分析

时间复杂度：O(log n)。每次循环将搜索范围减半，最多执行 log₂n 次。
空间复杂度：O(1)。只使用了常数个额外变量。

mid = left + (right - left) / 2 这种写法避免了 (left + right) / 2 可能导致的整数溢出问题。当 left 和 right 都接近 Integer.MAX_VALUE 时，两者相加会溢出，而 right - left 不会超过数组长度，绝对安全。

三、解法二：左闭右开区间 `[left, right)`

思路分析

左闭右开意味着：左端点 left 在搜索范围内，右端点 right 不在搜索范围内。可以理解为 right 是"哨兵"，它标记了搜索区间的右边界之外的第一个位置。

初始化时，right = nums.length，因为 nums.length 这个下标本身不在数组中，恰好充当"哨兵"。

循环条件用 while (left < right)，因为当 left == right 时，区间 [left, right) 为空，没有元素需要搜索，退出循环。

更新边界时：

如果 nums[mid] > target，说明目标在左半部分，mid 本身被排除，新的搜索范围右端点变为 mid（不包含），所以 right = mid。
如果 nums[mid] < target，说明目标在右半部分，mid 本身被排除，所以 left = mid + 1。

注意这里 right = mid 而不是 right = mid - 1，这是因为 right 本来就是开区间的右端点，它不参与搜索，直接赋值 mid 就把 mid 排除出去了。

完整代码

public class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;  // 右边界不在搜索区间内，充当哨兵

        while (left < right) {  // 区间为空时退出
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid;  // mid 排除，右边界直接设为 mid（开区间不含 mid）
            } else {
                left = mid + 1;  // mid 排除，左边界右移
            }
        }

        return -1;
    }
}

复杂度分析

时间复杂度：O(log n)。每次循环将搜索范围减半。
空间复杂度：O(1)。

四、解法三最优：统一写法——理解本质后的"万能模板"

两种写法的本质是什么？

很多人在纠结用哪种写法，其实这两种写法在逻辑上是完全等价的，只是对"搜索区间"的定义不同而已。理解了这一点，你就能推导出任何一种写法，不再需要死记硬背。

核心问题只有三个：

right 初始化为多少？（取决于右端点是否在搜索范围内）
循环条件是 < 还是 <=？（取决于 left == right 时区间是否为空）
更新时 right = mid 还是 right = mid - 1？（取决于 mid 是否被排除）

这三个问题的答案，完全由你选择的区间定义决定，三者之间是强耦合的。选定了其中一个，另外两个就确定了。

下面我用一个"循环不变量"的思维方式来写一个更清晰的统一模板。

Mermaid 图：二分查找决策流程

统一理解框架下的代码

我最推荐的写法是"左闭右开"模板，因为它和 C++ STL 的 lower_bound、upper_bound，以及 Java 的 Arrays.binarySearch 底层逻辑是一致的，便于后续扩展到更复杂的二分场景。

public class BinarySearchUnified {

    /**
     * 统一的左闭右开写法
     * 搜索区间 [left, right)，right 始终是"还未确认是答案"的第一个位置
     */
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] < target) {
                // mid 肯定不是答案，且 mid 左边的都不是，left 右移
                left = mid + 1;
            } else {
                // nums[mid] >= target，mid 可能是答案，不能排除 mid
                // 但 mid+1 及其右边都不可能是"第一个"，right 移到 mid
                right = mid;
            }
        }

        // 循环结束时 left == right，这是第一个 >= target 的位置
        // 判断是否正好等于 target
        if (left < nums.length && nums[left] == target) {
            return left;
        }
        return -1;
    }

    /**
     * lower_bound：第一个 >= target 的位置（仿照 C++ STL）
     * 这是二分查找的核心原语，其他变种都能从这里派生
     */
    public int lowerBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length;  // 注意：right = length，左闭右开

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;  // 返回第一个 >= target 的下标，如果不存在则返回 nums.length
    }

    /**
     * upper_bound：第一个 > target 的位置（仿照 C++ STL）
     */
    public int upperBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;  // 返回第一个 > target 的下标
    }

    public static void main(String[] args) {
        BinarySearchUnified sol = new BinarySearchUnified();
        int[] nums = {-1, 0, 3, 5, 9, 12};

        System.out.println(sol.search(nums, 9));    // 输出 4
        System.out.println(sol.search(nums, 2));    // 输出 -1
        System.out.println(sol.lowerBound(nums, 3)); // 输出 2
        System.out.println(sol.upperBound(nums, 3)); // 输出 3
    }
}

复杂度分析

时间复杂度：O(log n)。每次循环，right - left 至少减少一半。
- 初始时区间大小为 n
- 每次 mid = left + (right - left) / 2，无论走哪个分支，right - left 都至少减少一半
- 因此最多 ⌈log₂n⌉ 次循环
空间复杂度：O(1)。

五、举一反三：同类题与模板应用

掌握了这套统一模板之后，很多题目都能套用。

同类题目列表：

题号	题目	关键点
35	搜索插入位置	直接返回 `lowerBound(nums, target)`
34	查找第一个和最后一个位置	`lowerBound` + `upperBound - 1`
69	x 的平方根	在答案空间 `[0, x]` 上二分
74	搜索二维矩阵	把二维矩阵映射到一维再二分
278	第一个错误的版本	`lowerBound` 变种，条件改为 `isBadVersion(mid)`

通用模板总结：

// 模板一：找到精确值，找不到返回 -1（左闭右闭）
int binarySearchExact(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

// 模板二：找第一个满足条件的位置（左闭右开）
// condition(mid) 为 true 时，mid 有可能是答案，缩小 right
// condition(mid) 为 false 时，mid 不是答案，扩大 left
int binarySearchFirst(int[] nums, Predicate<Integer> condition) {
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (condition.test(mid)) right = mid;
        else left = mid + 1;
    }
    return left;
}

六、踩坑实录

坑一：`mid = (left + right) / 2` 导致整数溢出

这是我遇到的第一个坑，当时在生产环境里处理一个大数组，数组长度接近 Integer.MAX_VALUE / 2，结果 left + right 溢出了，mid 变成了负数，直接数组越界。

从那以后我就记住了：一定要写 mid = left + (right - left) / 2，或者用无符号右移 mid = (left + right) >>> 1。后者利用了 Java 无符号右移的特性，即使 left + right 溢出，右移一位之后结果依然正确，因为溢出的最高位被移走了。

坑二：混用两种区间定义导致死循环

这是最常见的坑，也是最难发现的。比如有人用左闭右开的初始化（right = nums.length），但循环条件写成了左闭右闭的 left <= right，更新时又用了 right = mid - 1。这三个地方来自两套不同的逻辑体系，混在一起必然出错。

我当时为了记住这件事，专门画了一张表格贴在显示器旁边：

区间类型    初始 right         循环条件        right 更新
[l, r]     nums.length-1     l <= r         mid - 1
[l, r)     nums.length       l < r          mid

三行三列，全部对应，不能乱搭。

坑三：循环内修改变量后忘记重新计算 mid

这个坑我见过有人用 do-while 改写二分，在 do 里面先用 mid，再更新 left/right，然后 while 里直接用了上一轮的 mid 做判断。二分查找的 mid 必须在每次循环开始时重新计算，这是不变的规律。

坑四：对只有一个元素的数组没有做边界检查

lowerBound 返回的是"第一个 >= target 的位置"，这个位置可能等于 nums.length，表示所有元素都小于 target。如果没有判断 left < nums.length 就直接访问 nums[left]，会导致数组越界。我在刚开始用这个模板时，就因为漏掉这个检查被坑了一次。

坑五：把"找第一个满足条件"和"找最后一个满足条件"混淆

找"第一个满足条件"（即 lowerBound）时，condition(mid) 为真时要缩小右边界：right = mid。找"最后一个满足条件"时，需要用 upperBound - 1 来间接计算，不能直接用 lowerBound 的逻辑去倒推。

我曾经想直接写一个"找最后一个满足条件"的模板，结果陷入了边界条件的泥潭。最后的结论是：把所有问题都转化为 lowerBound 和 upperBound 的组合，是最可靠的做法。

七、总结

二分查找的核心不是"把数组对半折"，而是维护一个不变量：目标值如果存在，一定在当前搜索区间内。每次循环都要保证这个不变量成立，同时让区间缩小。

两种写法的对比：

维度	左闭右闭 `[l,r]`	左闭右开 `[l,r)`
初始化	`right = n-1`	`right = n`
循环条件	`left <= right`	`left < right`
right 更新	`right = mid-1`	`right = mid`
退出时含义	区间为空	区间为空
扩展性	仅用于精确查找	可扩展为 lower/upper_bound

我个人的建议是：日常写题优先用左闭右开模板，然后把 search(target) 理解为 lowerBound(target) + 边界检查。这样不仅能解决 704 这道基础题，还能自然地迁移到 34、35、875 等更复杂的二分题目上，不需要针对每道题重新推导边界条件。

记住这句话：选定区间定义，推导所有细节；不要靠感觉，要靠逻辑。