力扣hot100：搜索二维矩阵与在排序数组中查找元素的第一个和最后一个位置（74，34）

问题描述

算法思路

利用矩阵的特性，我们可以采用两次二分查找：

1. 定位目标行：找到最后一个首元素小于等于 target 的行
2. 在目标行查找：在该行中进行标准二分查找

时间复杂度：O(log m + log n) 空间复杂度：O(1)

代码实现

class Solution { public boolean searchMatrix(int[][] matrix, int target) { int rows= matrix.length;; int length = matrix[0].length; int row_left=0; int row_right=rows-1; int row_target=0; while (row_left<=row_right){ int temp=(row_right-row_left)/2+row_left; if(targetmatrix[temp][0]){ row_left=temp+1; row_target=temp; }else{ row_target=temp; break; } } int column_left=0; int column_right=length-1; while(column_left<=column_right){ int temp=(column_right-column_left)/2+column_left; if(targetmatrix[row_target][temp]){ column_left=temp+1; }else if(target==matrix[row_target][temp]){ return true; } } return false; }}

关键点解析

1. 行定位技巧：

   • 寻找最后一个满足 matrix[i] <= target 的行
   • 通过 high 指针记录最终目标行
   • 若 high < 0 表示所有行首元素均大于 target

2. 二分查找优化：

   • 行定位时：mid 计算防止整数溢出
   • 列查找时：标准二分模板确保高效性

3. 边界处理：

   • 空矩阵检查（matrix == null || length == 0）
   • 目标行不存在时的快速返回（high < 0）

示例分析

以矩阵 [[1,3,5,7],[10,11,16,20],[23,30,34,60]] 和 target = 3 为例：

1. 定位目标行：
   • 第一行首元素 1 ≤ 3 ⇒ high 指向第 0 行
   • 第二行首元素 10 > 3 ⇒ 锁定第 0 行
2. 行内查找：
   • 在第 0 行中找到元素 3 ⇒ 返回 true

总结

这道题通过两次二分查找充分利用了矩阵的有序特性：

1. 第一次二分在 O(log m) 时间内定位目标行
2. 第二次二分在 O(log n) 时间内完成行内查找

相较于直接遍历所有元素的 O(mn) 暴力解法，二分法将效率提升到对数级别，是处理有序矩阵的经典思路。

题目描述

解题思路

题目要求高效地在有序数组中定位元素的首次和最后一次出现位置，二分查找是最优选择。核心思想是通过两次二分查找：

1. 查找第一个位置：当找到 target 时，继续向左半部分搜索（缩小右边界）。
2. 查找最后一个位置：当找到 target 时，继续向右半部分搜索（增大左边界）。

关键点分析

• 时间复杂度 O(log n)：两次二分查找均遵守对数时间复杂度。
• 边界处理：空数组直接返回 [-1, -1]。
• 二分查找变种：
  • 查找左边界时，相等则压缩右边界（right = mid - 1）。
  • 查找右边界时，相等则压缩左边界（left = mid + 1）。

代码实现

class Solution { public int[] searchRange(int[] nums, int target) { int start=-1; int end=-1; if(nums.length==0){ return new int[] {start,end}; } start=searchFirst(nums,target); end=searchFinal(nums,target); return new int[] {start,end}; } private int searchFinal(int[] nums, int target) { int left=0; int right=nums.length-1; int result=-1; while(left<=right){ int temp=(right-left)/2+left; if(targetnums[temp]){ left=temp+1; }else if(target==nums[temp]){ result=temp; left=left+1; } } return result; } private int searchFirst(int[] nums, int target) { int left=0; int right=nums.length-1; int result=-1; while(left<=right){ int temp=(right-left)/2+left; if(targetnums[temp]){ left=temp+1; }else if(target==nums[temp]){ result=temp; right=right-1; } } return result; }}

算法流程详解

1. 初始化：检查数组是否为空，直接处理边界情况。
2. 查找左边界：
   • 当 nums[mid] < target 时，说明目标在右侧，更新 left = mid + 1。
   • 当 nums[mid] == target 时，记录位置并压缩右边界（right = mid - 1），继续向左搜索更早出现的位置。
3. 查找右边界：
   • 当 nums[mid] > target 时，说明目标在左侧，更新 right = mid - 1。
   • 当 nums[mid] == target 时，记录位置并压缩左边界（left = mid + 1），继续向右搜索更晚出现的位置。
4. 返回结果：组合左右边界的结果返回。

复杂度分析

• 时间复杂度：O(log n)，两次独立的二分查找。
• 空间复杂度：O(1)，仅使用常数级额外空间。

总结

本题通过二分查找的变种高效解决了有序数组中定位元素边界的问题。关键在于理解两种边界搜索的方向调整策略：

• 左边界搜索：相等时向左压缩（right = mid - 1）。
• 右边界搜索：相等时向右压缩（left = mid + 1）。

掌握这一技巧，即可轻松应对类似的二分查找变种问题！