算法二刷复盘｜LeetCode 3474 二分查找双杀（区间边界 + 二维矩阵）

目录一、LeetCode 34在排序数组中查找元素的第一个和最后一个位置题目描述核心思路两次二分分别锁定左右边界Java 完整实现复杂度分析二、LeetCode 74搜索二维矩阵题目描述核心思路二维降维直接二分Java 完整实现复杂度分析三、两道题的二分核心对比四、二刷复盘感悟二刷二分查找把两道高频变形题放在一起复盘一道是一维排序数组的区间边界查找一道是二维有序矩阵的降维二分。都是面试常考的二分应用场景吃透这两道就能掌握二分的核心变形技巧。一、LeetCode 34在排序数组中查找元素的第一个和最后一个位置题目描述给定一个升序排列的整数数组nums和目标值target找出目标值在数组中的开始和结束位置若不存在返回[-1, -1]。要求算法时间复杂度为 O (log n)。核心思路两次二分分别锁定左右边界普通二分只能找到任意一个等于target的位置这道题的关键是边界控制找左边界当nums[mid] target时继续向左收缩右边界直到找到第一个等于target的位置找右边界当nums[mid] target时继续向右收缩左边界直到找到最后一个等于target的位置特殊处理若左边界不存在即nums[left] ! target直接返回[-1,-1]。Java 完整实现java运行class Solution { public int[] searchRange(int[] nums, int target) { int left findLeftBound(nums, target); if (left -1) { return new int[]{-1, -1}; } int right findRightBound(nums, target); return new int[]{left, right}; } // 找左边界第一个等于target的位置 private int findLeftBound(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) { left mid 1; } else if (nums[mid] target) { right mid - 1; } else { // 等于target时继续往左找收缩右边界 right mid - 1; } } // 检查边界是否越界且值是否匹配 if (left nums.length nums[left] target) { return left; } return -1; } // 找右边界最后一个等于target的位置 private int findRightBound(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) { left mid 1; } else if (nums[mid] target) { right mid - 1; } else { // 等于target时继续往右找收缩左边界 left mid 1; } } // 检查边界是否越界且值是否匹配 if (right 0 nums[right] target) { return right; } return -1; } }复杂度分析时间复杂度O (log n)两次二分查找整体仍为对数级复杂度空间复杂度O (1)原地操作无额外空间开销。二、LeetCode 74搜索二维矩阵题目描述编写高效算法判断m x n矩阵中是否存在目标值。矩阵特性每行从左到右升序排列每行第一个整数大于前一行的最后一个整数。核心思路二维降维直接二分这道题的矩阵是严格有序的将矩阵按行拼接后就是一个一维升序数组因此可以直接用普通二分解决关键是一维索引与二维坐标的转换一维索引mid对应的二维行号row mid / nn为矩阵列数一维索引mid对应的二维列号col mid % n。Java 完整实现java运行class Solution { public boolean searchMatrix(int[][] matrix, int target) { // 边界处理空矩阵/空行/空列 if (matrix null || matrix.length 0 || matrix[0].length 0) { return false; } int m matrix.length; int n matrix[0].length; int left 0; int right m * n - 1; while (left right) { int mid left (right - left) / 2; // 转换为二维坐标 int row mid / n; int col mid % n; if (matrix[row][col] target) { return true; } else if (matrix[row][col] target) { left mid 1; } else { right mid - 1; } } return false; } }复杂度分析时间复杂度O (log (m*n))与普通二分一致复杂度为对数级空间复杂度O (1)原地操作无额外空间开销。三、两道题的二分核心对比表格题目核心考点关键技巧面试高频问题34. 区间边界查找二分的边界变形两次二分区分左右边界的收缩方向如何处理 target 不存在的情况左右边界的二分模板怎么写74. 二维矩阵搜索二分的降维应用二维坐标与一维索引的转换若矩阵不严格有序如 “Z” 字形有序还能用这种方法吗四、二刷复盘感悟二分的核心是「边界控制」34 题最容易出错的就是边界处理尤其是等于target时的收缩方向以及循环结束后的边界检查。统一使用「左闭右闭」模板能大幅降低出错概率二分的本质是「有序数据的快速定位」只要数据是有序的不管是一维还是二维都可以用二分优化。74 题就是典型的将二维有序转化为一维有序再用二分解决面试常考变形拓展除了这两道「旋转排序数组的二分」「山脉数组的二分」也是高频考点掌握通用模板就能举一反三