LeetCode 704. 二分查找

约 4 分钟
文章信息 22 个分类 2 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 100-200 腾讯 字节 阿里 华为 微软 美团 拼多多 京东 小米 百度 小红书 快手 滴滴 B站 虾皮 猿辅导
标签
数组 二分查找

题目描述

✅ 704. 二分查找

image-20260928190708333

题意分析

在一个按升序排列、元素互不相同的整数数组 nums 中查找 target。如果存在，返回它的下标；否则返回 -1。返回的是位置，不是元素值，也不是目标本应插入的位置。

数组已经有序，因此比较一个位置后，可以判断目标只能出现在它的左侧还是右侧，无需逐个检查所有元素。

解法：闭区间二分查找

核心思路

[!blue]

用闭区间 [left, right] 表示尚未排除的下标范围，两个端点都包含在内。始终维护一个条件：如果目标存在且还未被找到，它一定在这个区间中。开始时把整个数组作为候选范围，即 left = 0、right = n - 1。

每轮检查中点 mid。若 nums[mid] == target，直接返回。若 nums[mid] < target，由于数组升序，mid 及其左侧的值都不可能等于目标，所以新范围从 mid + 1 开始。若 nums[mid] > target，同理排除 mid 及其右侧，新右边界为 mid - 1。每次删除的都是确定不可能的位置，上面的条件始终成立。

left == right 时仍剩下一个尚未检查的位置，因此循环条件必须是 left <= right。只有 left > right 才表示候选区间为空；此时还没找到目标，就能确定它不存在，返回 -1。

中点使用 left + (right - left) / 2，避免直接相加两个下标可能造成的整数溢出。每轮都会排除已检查的中点，并把候选范围缩小约一半，所以能够在对数时间内结束。

解题步骤

  1. 初始化闭区间 [0, nums.length - 1]。
  2. 当 left <= right 时，计算 mid = left + (right - left) / 2。
  3. 若中点值等于目标，返回 mid；若小于目标，令 left = mid + 1；若大于目标，令 right = mid - 1。
  4. 区间为空后退出循环，返回 -1。

代码实现

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;
            }

            if (nums[mid] < target) {
                // 中点已经检查过，连同不可能的一侧一起排除。
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    // 闭区间剩下一个位置时，仍需检查最后一个候选。
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        }
        if nums[mid] < target {
            // 中点已经检查过，连同不可能的一侧一起排除。
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

复杂度分析

  • 时间复杂度：$O(\log n)$，其中 n 为数组长度。每轮只做常数次比较，并排除约一半候选位置。
  • 空间复杂度：$O(1)$，只维护左右边界和中点，不创建子数组。

关键点总结

[!green]

  • 先确定候选区间是否包含端点，再统一初始化、循环条件和边界更新方式。
  • 本实现采用闭区间，必须配套使用 right = n - 1、left <= right 和 mid ± 1。
  • 更新边界的依据是数组有序性：排除的整段都不可能包含目标，而非仅凭中点大小猜测方向。

易错点总结

[!yellow]

  • 把循环条件写成 left < right，会漏查最后一个位置。
  • 把右边界初始化为数组长度，会访问越界。
  • 更新为 left = mid 或 right = mid，可能导致死循环。
  • 未找到时应返回 -1，不要误返回插入位置 left。

相似题目

题目 难度 关联与区别
35. 搜索插入位置 简单 本题可以在相等时返回，原题还要在不存在时给出插入边界。
34. 在排序数组中查找元素的第一个和最后一个位置 中等 有重复值时普通二分只找任意一个，本题的边界扩展可用于寻找最左与最右位置。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/03031453
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！