经典150题 - 二分查找

33. 搜索旋转排序数组

整数数组在某个未知点进行了旋转（数值互不相同）。在数组中查找目标值 target 并返回其下标，不存在则返回 -1。要求 $O(\log n)$。

var search = function(nums, target) {
    let left = 0;
    let right = nums.length - 1; // 闭区间 [left, right]
 
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
 
        // 1. 命中目标直接返回
        if (nums[mid] === target) {
            return mid;
        }
 
        // 2. 核心分支：旋转数组切开后，左右必有一半是严格升序的
        if (nums[left] <= nums[mid]) {
            // [left, mid] 左半段有序
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1; // target 落在左半段，收缩右边界
            } else {
                left = mid + 1;  // 否则必在右半段，收缩左边界
            }
        } else {
            // [mid, right] 右半段有序
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;  // target 落在右半段，收缩左边界
            } else {
                right = mid - 1; // 否则必在左半段，收缩右边界
            }
        }
    }
 
    return -1; // 区间缩尽未找到
};

复杂度：时间 O(log n)，空间 O(1)。

关键套路：

• 局部有序分治：旋转数组任意位置一分为二，nums[left] <= nums[mid] 成立则左半段严格单调递增，否则右半段单调递增。
• 开闭边界对称性：开头先排除 nums[mid] === target，所以 mid 端点为开区间；外端点 left / right 包含潜在目标，必须带等号（nums[left] <= target 与 target <= nums[right]）。

易错点：

• left === mid：区间只剩 1~2 个元素时 mid === left，判断左半段有序必须用 <=（nums[left] <= nums[mid]）。
• 右端点漏等号：在右半段分支中，手滑写成 target < nums[right] 会漏掉恰在右边界的目标值，必须为 target <= nums[right]。

---

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个非递减整数数组 nums 和目标值 target。找出 target 的开始位置和结束位置；不存在则返回 [-1, -1]。要求 $O(\log n)$。

var searchRange = function(nums, target) {
    // 闭包辅助二分：isFirst 控制向左挤压还是向右挤压
    const findBound = (isFirst) => {
        let left = 0;
        let right = nums.length - 1; // 闭区间 [left, right]
        let anchor = -1;             // 暂存最佳答案
 
        while (left <= right) {
            // 防溢出中点计算
            const mid = left + Math.floor((right - left) / 2);
 
            if (nums[mid] === target) {
                anchor = mid; // 暂存当前命中位置
                if (isFirst) {
                    right = mid - 1; // 找最左边界：继续向左收缩
                } else {
                    left = mid + 1;  // 找最右边界：继续向右收缩
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
 
        return anchor;
    };
 
    // 1. 查找最左边界
    const first = findBound(true);
    // Fail-Fast 剪枝：若左边界不存在，说明 target 根本不在数组中，直接返回 [-1, -1]
    if (first === -1) {
        return [-1, -1];
    }
 
    // 2. 查找最右边界
    const last = findBound(false);
    return [first, last];
};

复杂度：时间 O(log n)，空间 O(1)。

关键套路：

• 暂存答案（Ans 模式）：命中 target 后不立即退出，用变量记录当前位置，并根据目标方向（向左或向右）持续压缩边界，直至区间缩尽。
• Fail-Fast 剪枝：若最左边界返回 -1，说明数组中无此元素，立即短路返回 [-1, -1]，省去第二次无效二分。

易错点：

• 禁止线性探查：命中 mid 后切忌用 while 左右线性扩展找边界，在全同数组下会退化为 $O(n)$。
• 中点算术防溢出：避免写成 left + (left + right) / 2 导致越界溢出。

---

35. 搜索插入位置

在有序数组中找到目标值并返回索引；若不存在，返回它按顺序插入的位置。要求 $O(\log n)$。

var searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length - 1; // 闭区间 [left, right]
 
    while (left <= right) {
        // 防止 (left + right) 大数溢出
        const mid = left + Math.floor((right - left) / 2);
 
        if (nums[mid] === target) {
            return mid; // 命中目标直接返回
        } else if (nums[mid] < target) {
            left = mid + 1; // target 在右半边，缩小至 [mid + 1, right]
        } else {
            right = mid - 1; // target 在左半边，缩小至 [left, mid - 1]
        }
    }
 
    // 循环结束时必定有 left = right + 1
    // 此时 nums[0 ... left-1] < target，且 nums[left ... n-1] > target
    // 因此 target 插入的位置恰好就是 left
    return left;
};

复杂度：时间 O(log n)，空间 O(1)。

关键套路：

• 闭区间三要素：初始化 right = n - 1，循环条件 left <= right，收缩 left = mid + 1 / right = mid - 1。
• 返回值意义：未命中退出时，left 指向第一个大于 target 的位置，天然就是插入点。

---

74. 搜索二维矩阵

每行升序且每行首元素大于上一行尾元素，判断 $m\times n$ 矩阵中是否存在目标值。要求 $O(\log (m\times n))$。

var searchMatrix = function(matrix, target) {
    const m = matrix.length;
    const n = matrix[0].length;
 
    let left = 0;
    let right = m * n - 1; // 将 m * n 的矩阵视作长度为 m * n 的一维有序数组
 
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
 
        // 核心映射公式：一维下标转二维坐标
        const row = Math.floor(mid / n);
        const col = mid % n;
        const val = matrix[row][col];
 
        if (val === target) {
            return true;
        } else if (val < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
 
    return false;
};

复杂度：时间 O(log(m × n))，空间 O(1)。

关键套路：

• 二维展平映射：一维下标 index 对应二维坐标 [Math.floor(index / n), index % n]，将二维矩阵降维为一维二分。

---

153. 寻找旋转排序数组中的最小值

升序数组在未知点发生旋转且元素互不相同。找出数组中的最小值。要求 $O(\log n)$。

var findMin = function(nums) {
    let left = 0;
    let right = nums.length - 1; // 闭区间 [left, right]
 
    // 当区间只剩 1 个元素时退出，两指针汇聚在最小值上
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
 
        if (nums[mid] > nums[right]) {
            // mid 大于右端点：断崖与最小值必在右半区，且 mid 绝不是最小值
            left = mid + 1;
        } else {
            // mid 小于右端点：[mid, right] 严格升序，最小值可能就是 mid 本身，保留 mid
            right = mid;
        }
    }
 
    return nums[left];
};

复杂度：时间 O(log n)，空间 O(1)。

关键套路：

• 右端点黄金参考系：以 nums[right] 为基准无需考虑数组是否旋转；若以 nums[left] 为基准在完全未旋转的递增数组中会产生二义性。
• 保留 mid 的收敛设计：right = mid 保留候选解，配合 while (left < right) 保证区间严格单调缩小且不越界死循环。

---

162. 寻找峰值

峰值元素严格大于左右相邻值，两端为 $-\infty$。在无序数组中找到任意一个峰值并返回其索引。要求 $O(\log n)$。

var findPeakElement = function(nums) {
    let left = 0;
    let right = nums.length - 1; // 闭区间 [left, right]
 
    // 只要区间内还有两个及以上元素，就继续爬坡
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
 
        if (nums[mid] < nums[mid + 1]) {
            // 处于上坡阶段：峰值必定在右侧，且 mid 绝不是峰值，排除 mid
            left = mid + 1;
        } else {
            // 处于下坡阶段：峰值在左侧，或 mid 本身就是峰值，保留 mid
            right = mid;
        }
    }
 
    // 最终 left === right，两指针收敛在峰顶
    return left;
};

复杂度：时间 O(log n)，空间 O(1)。

关键套路：

• 局部单调性（二分不一定要求全局有序）：比较 nums[mid] 与 nums[mid + 1]，沿「上坡」方向推进必定能找到山顶。
• 边界与收敛：while (left < right) 保证 mid < right，mid + 1 绝不越界；right = mid 保证区间严格缩小，不发生死循环。

---

核心方法论：二分查找两大心智模型

维度	确定值查找（33, 34, 35, 74）	极值/分界点收敛（153, 162）
核心隐喻	安检排查（目标可能不存在）	淘汰赛/幸存者游戏（目标必定存在）
区间定义	闭区间 [left, right]	闭区间 [left, right]
循环条件	while (left <= right)	while (left < right)
右界收缩	right = mid - 1	right = mid（因 mid 仍可能是答案）
停机状态	指针交错 left === right + 1，区间为空	指针重合 left === right，仅剩 1 个元素
答案提取	循环内命中提前 return，或利用出界后的 left 插入点	循环外直接返回幸存者 nums[left]

相关笔记

• Hot100 二分查找专题
• 经典 150 分治