二分查找进阶：搜索二维矩阵 查找元素首尾位置 深度解析

目录一、搜索二维矩阵LeetCode 74・中等题目描述解题思路Java 代码实现标准二分版复杂度分析核心知识点总结二、在排序数组中查找元素的第一个和最后一个位置LeetCode 34・中等题目描述解题思路Java 代码实现两次二分版复杂度分析核心知识点总结一、搜索二维矩阵LeetCode 74・中等题目描述编写一个高效的算法来判断m x n矩阵中是否存在一个目标值。该矩阵具有如下特性每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。示例plaintext输入matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target 3 输出true解题思路这道题的核心是将二维矩阵「拉平」为一维有序数组用标准二分查找解决矩阵特性由于每行升序且行首大于上一行行尾整个矩阵本质是一个一维升序数组。坐标映射对于一维下标mid对应二维坐标为行号row mid / nn为矩阵列数列号col mid % n标准二分用一维二分查找的逻辑通过坐标映射访问矩阵元素判断是否等于目标值。Java 代码实现标准二分版java运行public class SearchMatrix { 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; int num matrix[row][col]; if (num target) { return true; // 找到目标值 } else if (num target) { left mid 1; // 目标在右半区 } else { right mid - 1; // 目标在左半区 } } return false; // 未找到 } }复杂度分析时间复杂度O(log(mn))等价于一维数组的二分查找每次将搜索范围缩小一半。空间复杂度O(1)仅使用常数级额外空间。核心知识点总结坐标映射公式row mid / ncol mid % n是二维转一维的关键。边界处理和一维二分完全一致闭区间[left, right]循环条件left right。适用场景仅适用于行升序、行首大于上一行行尾的矩阵若矩阵仅每行升序、列升序如 LeetCode 240需用其他方法。二、在排序数组中查找元素的第一个和最后一个位置LeetCode 34・中等题目描述给你一个按照非递减顺序排列的整数数组nums和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target返回[-1, -1]。你必须设计并实现时间复杂度为 O(logn) 的算法解决此问题。示例plaintext输入nums [5,7,7,8,8,10], target 8 输出[3,4] 输入nums [5,7,7,8,8,10], target 6 输出[-1,-1]解题思路这道题是二分查找的经典变形核心是用两次二分分别查找左边界和右边界查找左边界找到第一个等于target的元素下标。当nums[mid] target时不直接返回而是收缩右边界继续向左查找直到left指向第一个等于target的位置。查找右边界找到最后一个等于target的元素下标。当nums[mid] target时不直接返回而是收缩左边界继续向右查找直到right指向最后一个等于target的位置。结果校验若左边界越界或不等于target说明数组中无target返回[-1, -1]否则返回[leftBoundary, rightBoundary]。Java 代码实现两次二分版java运行public class SearchRange { public int[] searchRange(int[] nums, int target) { int leftBoundary findLeftBoundary(nums, target); int rightBoundary findRightBoundary(nums, target); // 校验左边界越界 或 左边界元素不等于target说明无目标值 if (leftBoundary nums.length || nums[leftBoundary] ! target) { return new int[]{-1, -1}; } return new int[]{leftBoundary, rightBoundary}; } /** * 查找target的左边界第一个等于target的下标 */ private int findLeftBoundary(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) { // 等于target时收缩右边界继续向左找 right mid - 1; } else { left mid 1; } } return left; // 循环结束left指向第一个等于target的位置 } /** * 查找target的右边界最后一个等于target的下标 */ private int findRightBoundary(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) { // 等于target时收缩左边界继续向右找 left mid 1; } else { right mid - 1; } } return right; // 循环结束right指向最后一个等于target的位置 } }复杂度分析时间复杂度O(logn)两次二分查找每次时间复杂度均为 O(logn)。空间复杂度O(1)仅使用常数级额外空间。核心知识点总结左右边界查找逻辑左边界nums[mid] target时right mid - 1最终left为左边界。右边界nums[mid] target时left mid 1最终right为右边界。结果校验必须校验左边界是否越界、是否等于target避免数组中无target时返回错误结果。边界处理闭区间写法循环条件left right和标准二分完全一致。