【LeetCode 74】算法：搜索二维矩阵

题目：
给你一个满足下述两条属性的 m x n 整数矩阵：
每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

问题中矩阵的每一行和每一列都是有序的，给定一个目标值 target，确定这个值是否存在于矩阵中。
可以利用矩阵的有序性质，通过在每一行内进行二分查找，减少搜索空间，提高查找效率。
算法思路：

• 从第一行开始：由于每行的第一个整数大于前一行的最后一个整数，我们可以从第一行的第一个元素开始查找。
  
• 二分查找：对于每一行，使用二分查找来确定 target 是否存在于该行中。如果找到，返回 true。
  
• 移动到下一行：如果当前行中没有找到 target，则由于矩阵的特性（每行的整数从左到右非严格递增排列），我们知道 target 不可能存在于该行之后的任何一行中。因此，我们可以安全地移动到下一行的第一个元素，并从那里开始新的二分查找。
  
• 继续或终止：重复步骤 2 和 3，直到找到 target 或遍历完整个矩阵。
  

复杂度分析：

• 时间复杂度：O(m * log n)，其中 m 是行数，n 是列数。对于每一行，最多执行一次二分查找，其时间复杂度为 O(log n)，最多遍历所有 m 行。
  
• 空间复杂度：O(1)，只使用了常数额外空间。
  

Java代码实现：

1. public class Solution {
2.     public boolean searchMatrix(int[][] matrix, int target) {
3.        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
4.            return false;
5.        }
7.        int rows = matrix.length;
8.        int cols = matrix[0].length;
10.        int row = 0;
11.        int col = cols - 1;
13.         while (row < rows && col >= 0) {
14.            if (matrix[row][col] == target) {
15.                return true;
16.            } else if (matrix[row][col] > target) {
17.                col--;
18.            } else {
19.                row++;
20.            }
21.        }
22.        return false;
23.    }
24. }

复制代码

来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除