当前位置：首页 > news >正文

LeetCode 热题 100 之 35. 搜索插入位置 74. 搜索二维矩阵 34. 在排序数组中查找元素的第一个和最后一个位置

news 2026/8/27 3:34:41

本次三道题目
35. 搜索插入位置
74. 搜索二维矩阵
34. 在排序数组中查找元素的第一个和最后一个位置

35. 搜索插入位置

class Solution { public int searchInsert(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; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } // 循环结束时 left 就是插入位置 return left; } }

解题思路: 二分查找

初始化left = 0，right = nums.length - 1（闭区间）。

循环条件：left <= right：

计算mid = left + (right - left) / 2（避免溢出）。
若nums[mid] == target：直接返回mid。
若nums[mid] < target：目标在右侧，left = mid + 1。
若nums[mid] > target：目标在左侧，right = mid - 1。

循环结束时，left就是目标值应插入的位置（此时left > right，left指向第一个大于 target 的位置）。

为什么会溢出？

在 Java 中，int类型的取值范围是[-2^31, 2^31 - 1]（即-2147483648 ~ 2147483647）。

直接计算(left + right) / 2：如果left和right都是接近2^31 - 1的大数（比如left = 2147483640，right = 2147483647），left + right会超出int的最大值，触发整数溢出，结果变成负数（比如2147483640 + 2147483647 = 4294967287，超出2^31 - 1，实际存储为-2147483641），导致mid计算错误。
计算left + (right - left) / 2：right - left是两个大数的差值，结果远小于2^31 - 1，不会溢出；再加上left，最终结果和(left + right) / 2等价，但完全避免了溢出风险。

74. 搜索二维矩阵

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

class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; int low = 0, high = m * n - 1; while (low <= high) { int mid = (high - low) / 2 + low; int x = matrix[mid / n][mid % n]; if (x < target) { low = mid + 1; } else if (x > target) { high = mid - 1; } else { return true; } } return false; } } 作者：力扣官方题解 链接：https://leetcode.cn/problems/search-a-2d-matrix/solutions/688117/sou-suo-er-wei-ju-zhen-by-leetcode-solut-vxui/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解题思路1:一次二分查找

把二维矩阵matrix[m][n]映射成一维数组：

一维索引idx对应二维坐标：
- 行号row = idx // n
- 列号col = idx % n
初始左指针left = 0，右指针right = m * n - 1
每次取中间值mid = (left + right) // 2，转换为二维坐标后和target比较：
- 若matrix[row][col] == target→ 找到，返回true
- 若matrix[row][col] < target→ 目标在右侧，left = mid + 1
- 若matrix[row][col] > target→ 目标在左侧，right = mid - 1
循环结束仍未找到 → 返回false

class Solution { public boolean searchMatrix(int[][] matrix, int target) { int rowIndex = binarySearchFirstColumn(matrix, target); if (rowIndex < 0) { return false; } return binarySearchRow(matrix[rowIndex], target); } public int binarySearchFirstColumn(int[][] matrix, int target) { int low = -1, high = matrix.length - 1; while (low < high) { int mid = (high - low + 1) / 2 + low; if (matrix[mid][0] <= target) { low = mid; } else { high = mid - 1; } } return low; } public boolean binarySearchRow(int[] row, int target) { int low = 0, high = row.length - 1; while (low <= high) { int mid = (high - low) / 2 + low; if (row[mid] == target) { return true; } else if (row[mid] > target) { high = mid - 1; } else { low = mid + 1; } } return false; } } 作者：力扣官方题解 链接：https://leetcode.cn/problems/search-a-2d-matrix/solutions/688117/sou-suo-er-wei-ju-zhen-by-leetcode-solut-vxui/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解题思路2:两次二分查找

由于每行的第一个元素大于前一行的最后一个元素，且每行元素是升序的，所以每行的第一个元素大于前一行的第一个元素，因此矩阵第一列的元素是升序的。

我们可以对矩阵的第一列的元素二分查找，找到最后一个不大于目标值的元素，然后在该元素所在行中二分查找目标值是否存在。

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

非递减有序数组（也叫 “非严格递增数组”）是指：数组中每个元素都大于或等于它前面的元素（nums[i] ≥ nums[i-1]，i > 0）。

class Solution { public int[] searchRange(int[] nums, int target) { int left = findLeft(nums, target); int right = findRight(nums, target); // 不存在的情况 if (left == nums.length || nums[left] != target) { return new int[]{-1, -1}; } return new int[]{left, right}; } // 找左边界：第一个 >= target 的位置 private int findLeft(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) { right = mid - 1; } else { left = mid + 1; } } return left; } // 找右边界：最后一个 <= target 的位置（比基于找到左边界再遍历快一点数据大的话） private int findRight(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 { right = mid - 1; } } return right; } }