题目描述

今天看一道最基础、也最容易写错边界的题：二分查找。

这题非常值得定期回顾，因为很多二分变形题，最后都是从这道题的边界更新逻辑扩展出来的。

这是一道典型的有序数组查找模板题。

题意理解

给你一个升序排列的数组和目标值 target。

要求你在数组里找到这个目标值的下标；如果不存在，就返回 -1。

一句话概括：

每次利用有序性，把搜索区间砍掉一半。

题目考查点

• 数据结构：数组

• 算法思想：二分查找

• 重点能力：如何稳定更新左右边界

• 容易出错的地方：循环条件和 left、right 更新写错

💻 算法 Code

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) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}

当前Java语言示例，更多语言请打开页面查看。

🎬 算法动画

动画讲解请看网站演示：网页链接 https://algo.lifestudylab.com/problems/binary-search

🧠 核心实现思路

先说结论：二分查找的关键不在于“会不会背模板”，而在于区间定义是否始终一致。

1. 为什么二分一定要求数组有序？

因为只有有序，比较 nums[mid] 和 target 才能推出目标值一定在哪一侧。

如果数组无序，砍掉一半区间就没有理论依据。

2. 这道题的区间定义是什么？

这里维护的是闭区间 [left, right]。

也就是说，只要 left <= right，就说明区间里还有元素需要继续检查。

3. 为什么 mid 这样写？

mid = left + (right - left) / 2

这种写法和 (left + right) / 2 含义一样，但更稳，能避免极端情况下的整型溢出。

4. 为什么更新边界要写成 mid + 1 和 mid - 1？

因为 mid 已经判断过了。

如果 nums[mid] < target，那目标只能在右边，所以左边界直接跳到 mid + 1；反过来同理。

5. 复杂度是多少？

• 时间复杂度：O(log n)

• 空间复杂度：O(1)

🎯 面试时忘记怎么办？

第一步：先说大方向

“这是有序数组查找，我会直接用二分。”

第二步：再说关键动作

“我维护闭区间 [left, right]。每次看中间值和目标值的关系，再决定保留左半边还是右半边。”

第三步：最后补复杂度

“每次都砍掉一半搜索区间，所以时间复杂度是 O(log n)。”

最后一定要点出关键点

二分最怕的不是不会写，而是边界定义前后不一致。

这道题最值得记住的一句话：

二分查找先定区间，再定循环条件，最后再写边界更新。

完整动画请点击左下角「阅读原文」。