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

目录

一、搜索二维矩阵（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

解题思路

这道题的核心是将二维矩阵「拉平」为一维有序数组，用标准二分查找解决：

1. 矩阵特性：由于每行升序且行首大于上一行行尾，整个矩阵本质是一个一维升序数组。
2. 坐标映射：对于一维下标mid，对应二维坐标为：
   • 行号：row = mid / n（n为矩阵列数）
   • 列号：col = mid % n
3. 标准二分：用一维二分查找的逻辑，通过坐标映射访问矩阵元素，判断是否等于目标值。

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)，仅使用常数级额外空间。

核心知识点总结

1. 坐标映射公式：row = mid / n，col = mid % n，是二维转一维的关键。
2. 边界处理：和一维二分完全一致，闭区间[left, right]，循环条件left <= right。
3. 适用场景：仅适用于行升序、行首大于上一行行尾的矩阵，若矩阵仅每行升序、列升序（如 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]

解题思路

这道题是二分查找的经典变形，核心是用两次二分分别查找左边界和右边界：

1. 查找左边界：找到第一个等于target的元素下标。
   • 当nums[mid] == target时，不直接返回，而是收缩右边界，继续向左查找，直到left指向第一个等于target的位置。
2. 查找右边界：找到最后一个等于target的元素下标。
   • 当nums[mid] == target时，不直接返回，而是收缩左边界，继续向右查找，直到right指向最后一个等于target的位置。
3. 结果校验：若左边界越界或不等于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)，仅使用常数级额外空间。

核心知识点总结

1. 左右边界查找逻辑：
   • 左边界：nums[mid] >= target时，right = mid - 1，最终left为左边界。
   • 右边界：nums[mid] <= target时，left = mid + 1，最终right为右边界。
2. 结果校验：必须校验左边界是否越界、是否等于target，避免数组中无target时返回错误结果。
3. 边界处理：闭区间写法，循环条件left <= right，和标准二分完全一致。